Précédent Index Suivant

Structures de données physiquement modifiables

Les valeurs des types suivants : vecteurs, chaînes de caractères, enregistrements à champs mutables et références sont des valeurs structurées dont les composants peuvent être physiquement modifiés.

Nous avons vu qu'une variable Objective CAML liée à une valeur garde cette valeur jusqu'à la fin de son existence. On ne peut modifier cette liaison que par une redéfinition et, dans ce cas, il ne s'agit pas à proprement parler de la << même >> variable puisque une nouvelle variable de même nom vient masquer l'ancienne qui n'est plus accessible directement mais qui reste inchangée. Avec les valeurs modifiables, on peut changer la valeur associée à une variable sans avoir à redéclarer cette dernière. On a accès à la valeur d'une variable aussi bien en lecture qu'en écriture.

Vecteurs

Les vecteurs, ou tableaux à une dimension, regroupent un nombre connu d'éléments de même type. On peut écrire directement un vecteur en énumérant ses valeurs encadrées par les symboles [| et |] et séparées par un point virgule à la manière des listes. 

# let v = [| 3.14; 6.28; 9.42 |] ;;
val v : float array = [|3.14; 6.28; 9.42|]
La fonction de création Array.create prend le nombre d'éléments du vecteur, une valeur initiale et retourne un nouveau vecteur. 

# let v = Array.create  3  3.14;;
val v : float array = [|3.14; 3.14; 3.14|]


L'accès et la modification d'un élément s'effectuent en précisant l'indice de l'élément désigné :

Syntaxe

expr1 . ( expr2 )

Syntaxe

expr1 . ( expr2 ) <- expr3


expr1 doit être un vecteur (type array) dont les valeurs sont du type de expr3. L'expression expr2 doit, bien entendu, être de type int. La modification est une expression de type unit. Le premier élément d'un vecteur a l'indice 0 et le dernier la longueur du vecteur moins 1. Les parenthèses entourant l'expression de l'indice sont obligatoires.

# v.(1) ;;
- : float = 3.14
# v.(0) <- 100.0 ;;
- : unit = ()
# v ;;
- : float array = [|100; 3.14; 3.14|]


Si l'indice utilisé pour accéder à un élément d'un tableau est en dehors de l'intervalle des indices de celui-ci, alors une exception sera déclenchée au moment de l'accès. 

# v.(-1) +. 4.0;;
Uncaught exception: Invalid_argument("Array.get")
Cette vérification est effectuée au moment de l'exécution du programme, ce qui peut ralentir l'exécution. Néanmoins elle est indispensable pour éviter de remplir des zones mémoire en dehors de l'espace alloué à un vecteur, ce qui provoquerait des erreurs d'exécution graves.

Les fonctions dédiées à la manipulation des tableaux font partie du module Array de la bibliothèque standard. On en donne la description au chapitre 8 (page ??). Nous utiliserons, dans les exemples ci-dessous, les trois fonctions suivantes du module Array :

Partage de valeurs dans un vecteur

Tous les éléments du vecteur contiennent la valeur passée à leur création. Cela implique un partage de cette valeur si celle-ci est une valeur structurée. Créons, par exemple une matrice comme vecteur de vecteurs à l'aide de la fonction create du module Array. 

# let v = Array.create 3 0;;
val v : int array = [|0; 0; 0|]
# let m = Array.create 3 v;;
val m : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]




Figure 3.1 : Représentation mémoire d'un vecteur partageant ses éléments

Si l'on modifie l'un des champs du vecteur v ayant servi à la création de m, on modifie du coup toutes les <<lignes>> de la matrice (voir les figures 3.1 et 3.2). 

# v.(0) <- 1;;
- : unit = ()
# m;;
- : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|]




Figure 3.2 : Modification d'éléments d'un vecteur partagé

Il y a duplication si la valeur d'initialisation du vecteur (second argument passé à Array.create) est une valeur immédiate et partage si cette valeur est une valeur structurée.

On appelle valeurs immédiates, les valeurs dont la taille ne dépasse pas la taille uniforme des valeurs d'Objective CAML, c'est à dire un mot mémoire. Ce sont les entiers, les caractères , les booléens et les constructeurs constants. Les autres valeurs, dites valeurs structurées, sont représentées par un pointeur sur une zone mémoire. Cette distinction est détaillée au chapitre 9 (page ??).
Les vecteurs de nombres flottants sont un cas particulier. Bien que les nombres flottants soient des valeurs structurées, la création d'un vecteur de flottants effectue une copie de la valeur initiale. Cela pour des questions d'optimisation. Le chapitre 12 sur l'interface avec le langage C (page ??) décrit ce cas particulier.

Matrices non rectangulaires

Une matrice, vecteur de vecteur, peut ne pas être rectangulaire. En effet rien n'empêche de modifier un des vecteurs éléments par un vecteur d'une autre longueur. Cela est utile pour limiter la taille d'une telle matrice. La valeur t suivante construit une matrice triangulaire pour les coefficients du triangle de Pascal. 

# let t = [| 
           [|1|];
           [|1; 1|];
           [|1; 2; 1|];
           [|1; 3; 3; 1|];
           [|1; 4; 6; 4; 1|];
           [|1; 5; 10; 10; 5; 1|]
         |] ;;
val t : int array array =
  [|[|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|]; [|1; 4; 6; 4; ...|]; ...|]
# t.(3) ;;
- : int array = [|1; 3; 3; 1|]
Dans cet exemple, l'élément du vecteur t à l'indice i est un vecteur d'entiers de taille i+1. Pour manipuler de telles matrices, il est nécessaire de calculer la taille de chaque élément vecteur.

Copie de vecteurs

Quand on copie un vecteur ou que l'on concatène deux vecteurs, le résultat obtenu est un nouveau vecteur. Une modification des vecteurs originaux n'entraîne pas de modification des copies, sauf, comme toujours à modifier les valeurs partagées. 

# let v2 = Array.copy v ;;
val v2 : int array = [|1; 0; 0|]
# let m2 = Array.copy m ;;
val m2 : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|]
# v.(1)<- 352;;
- : unit = ()
# v2;; 
- : int array = [|1; 0; 0|]
# m2 ;;
- : int array array = [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|]


On s'aperçoit dans cet exemple que la copie de m ne copie que les pointeurs vers v. Si un des éléments de v est modifié, alors m2 le sera aussi. La concaténation crée un nouveau vecteur dont la taille est égale à la somme des tailles des deux autres. 

# let mm = Array.append m m ;;
val mm : int array array =
  [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|];
    [|1; 352; ...|]; ...|]
# Array.length mm ;;
- : int = 6
# m.(0) <- Array.create 3 0 ;;
- : unit = ()
# m ;;
- : int array array = [|[|0; 0; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|]
# mm ;;
- : int array array =
[|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|];
  [|1; 352; ...|]; ...|]


Par contre la modification de v, valeur partagée dans m et mm, aura un effet sur ces deux matrices. 

# v.(1) <- 18 ;;
- : unit = ()
# mm;;
- : int array array =
[|[|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; ...|];
  ...|]


Chaînes de caractères

Les chaînes de caractères peuvent être considérées comme un cas spécial de vecteurs de caractères. Néanmoins pour des questions d'occupation mémoire1 leur type est spécialisé. De plus l'accès aux éléments possède une syntaxe particulière :

Syntaxe

expr1 . [expr2]
Les éléments d'une chaîne de caractères peuvent être modifiés physiquement :

Syntaxe

expr1 . [expr2] <- expr3 


# let s = "salut";;
val s : string = "salut"
# s.[2];;
- : char = 'l'
# s.[2]<-'Z';;
- : unit = ()
# s;;
- : string = "saZut"


Champs modifiables des enregistrements

Les champs d'un enregistrement peuvent être déclarés modifiables. Il suffit de l'indiquer dans la déclaration du type de l'enregistrement par le mot clé mutable.

Syntaxe

type nom = { ...; mutable nomi : t ; ...}


Voici un petit exemple définissant un type d'enregistrement pour les points du plan : 

# type point = { mutable xc : float; mutable yc : float } ;;
type point = { mutable xc: float; mutable yc: float }
# let p = { xc = 1.0; yc = 0.0 } ;;
val p : point = {xc=1; yc=0}


La valeur d'un champ déclaré mutable est donc modifiable suivant la syntaxe :

Syntaxe

expr1 . nom <- expr2


L'expression expr1 doit être d'un type enregistrement possédant la champ nom. L'opération de modification retourne une valeur de type unit. 

# p.xc <- 3.0 ;;
- : unit = ()
# p ;;
- : point = {xc=3; yc=0}


On peut écrire une fonction de déplacement d'un point, modifiant les coordonnées de celui-ci. On utilise la déclaration locale par filtrage pour séquentialiser les effets de bord. 

# let moveto p dx dy = 
   let () = p.xc <- p.xc +. dx 
   in p.yc <- p.yc +. dy ;;
val moveto : point -> float -> float -> unit = <fun>
# moveto p 1.1 2.2 ;;
- : unit = ()
# p ;;
- : point = {xc=4.1; yc=2.2}


Il est possible de mélanger des champs modifiables et des champs non modifiables dans la définition d'un enregistrement. Seuls ceux spécifiés mutable sont alors modifiables : 

# type t = { c1 : int; mutable c2 : int } ;;
type t = { c1: int; mutable c2: int }
# let r = { c1 = 0; c2 = 0 } ;;
val r : t = {c1=0; c2=0}
# r.c1 <- 1 ;;
Characters 0-9:
The label c1 is not mutable
# r.c2 <- 1 ;;
- : unit = ()
# r ;;
- : t = {c1=0; c2=1}


Nous donnons page ?? un exemple d'utilisation des enregistrements à champs modifiables et des tableaux pour implanter une structure de pile.

Références

Objective CAML fournit un type polymorphe ref qui peut être vu comme le type des pointeurs sur une valeur quelconque ; en Objective CAML, on parlera plutôt de référence sur une valeur. Une valeur référencée peut être modifiée. Le type ref est définit comme un enregistrement à un champ modifiable : 
type 'a ref = {mutable contents:'a}
Ce type est muni de raccourcis syntaxiques prédéfinis. On construit une référence sur une valeur par la fonction ref. La valeur référencée peut être atteinte par la fonction préfixe (!). La fonction modifiant le contenu d'une référence est la fonction infixe (:=). 

# let x = ref 3 ;;       
val x : int ref = {contents=3}
# x ;;
- : int ref = {contents=3}
# !x ;;    
- : int = 3
# x := 4 ;;               
- : unit = ()
# !x ;;
- : int = 4
# x := !x+1 ;;
- : unit = ()
# !x ;;
- : int = 5


Polymorphisme et valeurs modifiables

Le type ref est paramétré. C'est ce qui permet de l'utiliser pour créer des références sur des valeurs de n'importe quel type. Cependant, il faut apporter quelques restrictions au type des valeurs référencées : on ne peut pas autoriser la création d'une référence sur une valeur de type polymorphe sans prendre quelques précautions.

Supposons qu'il n'y ait aucune restriction, on pourrait alors déclarer : 
let x = ref [] ;;
La variable x serait alors de type 'a list ref et l'on pourrait en modifier la valeur de façon incohérente avec le typage statique fort d'Objective CAML : 

x := 1 :: !x ;; 
x := true :: !x ;;
On aurait ainsi une même variable de type int list à un moment et de type bool list à un autre.

Pour éviter une telle situation, le mécanisme d'inférence de type d'Objective CAML utilise une nouvelle catégorie de variables de type : les variables de type faible. Syntaxiquement, elles sont distinguées par le caractère souligné (_) qui les préfixe. 

# let x = ref [] ;;
val x : '_a list ref = {contents=[]}
La variable de type '_a n'est pas un paramètre de type, mais une inconnue en attente d'instanciation : c'est la première utilisation de x après sa déclaration qui fixera la valeur que prendra '_a et ce, dans tous les types qui en dépendent et de façon définitive : 

# x := 0::!x ;;
- : unit = ()
# x ;;
- : int list ref = {contents=[0]}
La variable x est désormais de type int list ref.

Un type contenant une inconnue est en fait monomorphe bien que son type n'ait pas été précisé. Il n'est pas possible d'instancier cette inconnue par un type polymorphe. 

# let x = ref [] ;;
val x : '_a list ref = {contents=[]}
# x := (function y -> ())::!x ;;
- : unit = ()
# x ;;
- : ('_a -> unit) list ref = {contents=[<fun>]}
Dans cet exemple, bien que nous ayons instancié l'inconnue de type avec un type a priori polymorphe ('a -> unit), le type est resté monomorphe avec une nouvelle inconnue de type.

Cette restriction du polymorphisme n'est pas réservée aux références mais s'applique à toute valeur contenant une partie modifiable : les vecteurs et les enregistrements ayant au moins un champ déclaré mutable, etc. Tous les paramètres de type, même ceux sans rapport avec une composante modifiable sont alors des variables de type faible. 

# type ('a,'b) t = { ch1 :'a list ; mutable ch2 : 'b list } ;;
type ('a, 'b) t = { ch1: 'a list; mutable ch2: 'b list }
# let x = { ch1 = [] ; ch2 = [] } ;;
val x : ('_a, '_b) t = {ch1=[]; ch2=[]}


Warning

Cette modification du typage de l'application a des conséquences sur les programmes fonctionnels purs.


Lorsque l'on applique une valeur polymorphe à une fonction polymorphe, on obtient également une variable de type faible, car il ne faut pas exclure que la fonction construise des valeurs physiquement modifiables. En d'autres termes, le résultat d'une application est toujours monomorphe. 

#  (function x -> x) []  ;;
- : '_a list = []


On obtient le même résultat avec l'application partielle : 

# let f a b = a ;;
val f : 'a -> 'b -> 'a = <fun>
# let g = f 1 ;;
val g : '_a -> int = <fun>


Pour retrouver un type polymorphe, il faut abstraire le second argument de f puis l'appliquer : 

# let h x = f 1 x ;;
val h : 'a -> int = <fun>


En effet, l'expression qui définit h est l'expression fonctionnelle function x -> f 1 x. Son évaluation produira une fermeture qui ne risque pas de produire d'effet de bord puisque le corps de la fonction n'est pas évalué.

De façon général, on distingue les expressions dites << non expansives >>, dont on est sûr que le calcul ne risque pas d'effectuer un effet de bord, des autres, dites << expansives >>. Le système de types d'Objective CAML classifie les expressions du langage selon leur forme syntaxique :
Précédent Index Suivant