Représentation interne des valeurs
Table des matières
1. Préambule

Les informations de typage incluent notamment les informations relatives aux structures des données manipulées (listes, enregistrements, constructeurs, entiers, chaînes, ...). Elles servent à générer le code qui créera et accèdera à de telles structures. Cette information de typage n'est pas conservée dans le code final (code-octet ou code natif).

Ce module a pour objectif de montrer comment sont représentées les valeurs OCaml en interne, surtout pour illustrer le partage de structures, la copie de valeurs et les références.

Nous ne décrivons pas tous les détails de la représentation interne, seulement quelques principes. Pour le reste, on pourra se référer à la partie du manuel OCaml sur l'interfaçage avec C.

Les illustrations de la représentation des valeurs en mémoire sont réalisées à l'aide de Caml-inspect, une bibliothèque permettant notamment de générer des graphes au format Graphviz, pour montrer les blocs et leur chaînage. La règle <ocaml-printf> et le plugin Dot de Stog font le reste pour la rédaction de ce document.

2. Représentation des valeurs
2.1. Entiers et pointeurs

Une valeur OCaml est représentée par un mot, de 32 ou 64 bits selon l'architecture matérielle sous-jacente.

Une valeur peut être soit un entier (unboxed integer), soit un pointeur. Cette distinction est faite avec le bit de plus faible poids: 1 pour un entier, 0 pour un pointeur. C'est la raison pour laquelle les entiers OCaml sont codés sur 31 ou 63 bits.

Un pointeur peut pointer un bloc dans le tas (heap, géré par le ramasse-miettes) ou bien un objet hors du tas (cas des allocations faites en C).

2.2. Blocs dans le tas

Chaque bloc du tas a un en-tête, composé de la longueur du bloc (en nombre de mots) et d'un tag. Ce tag indique la nature du bloc, donc la façon dont le bloc est structuré. On trouvera donc des tags pour distinguer notamment les blocs contenant une chaîne de caractères, une fermeture de fonction, un objet, ...

Les flottants sont représentés dans un bloc (boxed) sauf dans certains cas où il est possible d'optimiser la représentation en les mettant directement (unboxed).

Pour les types sommes (variants), chaque constructeur sera représenté selon qu'il possède ou non des arguments:

  • le premier constructeur sans argument sera représenté par l'entier 0, le second par 1, ..., le n-ième par l'entier (n-1),
  • le premier constructeur avec argument sera représenté par un bloc dans le tas avec le tag 0, le second avec le tag 1, ..., le n-ième avec le tag (n-1). Les champs du bloc contiennent les valeurs des arguments du constructeur. Il y a une limite au nombre de tags disponibles, ce qui limite le nombre de constructeurs possibles.

Les tuples et les enregistrements sont représentés par des blocs avec le tag 0. Les membres du tuple ou de l'enregistrement se trouvent successivement dans les champs du bloc (sauf pour les enregistrements où tous les champs sont des flottants, qui sont représentés comme un tableau de flottants). Dans le code généré, il n'y a donc pas de différence entre accéder à un élément d'un tuple et un champ d'un enregistrement.

Les tableaux d'entiers ou de pointeurs sont représentés par un bloc de tag 0, les tableaux de flottants par un bloc avec un tag spécial, permettant de mettre les flottants dans les champs du bloc, sans interpréter le contenu de ces champs comme étant "entier" ou "pointeur", ceci afin d'optimiser l'espace et les temps d'accès.

Parmi les constructeurs usuels,

  • (), false et [] sont représentés par l'entier 0, donc bien comme les premiers constructeurs constants de leurs types respectifs,
  • true est représenté par l'entier 1 (comme un deuxième constructeur constant du type bool),
  • h::t est représenté par un bloc avec le tag 0 et contenant deux champs, l'un pour la valeur de la tête h, l'autre avec la valeur de la queue t.
3. Exemples
3.1. Entiers, listes, chaînes

Commençons par associer à x la valeur 1 et à list une liste:

# let x = 1 ;;
val x : int = 1
# let list = [ x ; 2 ; 3];;
val list : int list = [1; 2; 3]
3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes Block(0): #2 1 BLK#2 3.1. Entiers, listes, chaînes Block(0): #2 2 BLK#2 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes Block(0): #2 3 0 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes Int: 1 3.1. Entiers, listes, chaînes list 3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes x 3.1. Entiers, listes, chaînes

Dans la représentation, nous constatons que la constante 1 n'est pas dans un bloc. La liste est bien représentée, comme décrit plus haut, par un chaînage de blocs avec le tag 0 et comportant chacun deux champs: la tête et la queue. Comme les valeurs de la liste sont des entiers, ils apparaissent directement dans le premier champ du bloc de chaque maillon. Le numéro sur la flèche entre deux blocs indique le numéro du champ du premier bloc qui pointe le second bloc (en commençant à 0). On constate que le dernier maillon de la liste contient 0 dans son dernier champ, ce qui représente le constructeur [].

Utilisons maintenant des chaînes de caractères:

# let x = "hello" ;;
val x : string = "hello"
# let list = [ x ; "world" ; "!"];;
val list : string list = ["hello"; "world"; "!"]
3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 BLK#2 3.1. Entiers, listes, chaînes String: 5 chars "hello" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 BLK#2 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes String: 5 chars "world" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 0 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes String: 1 char "!" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes list 3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes x 3.1. Entiers, listes, chaînes

Les chaînes étant représentées dans un bloc avec un tag spécial, on constate que x et le premier maillon de list pointent tous les deux vers le bloc contenant la chaîne. En effet, lorsqu'on met x dans la définition de la liste, c'est bien la valeur associée à x, donc ici l'adresse du bloc, qui est utilisée, ce qui aboutit au partage que l'on voit sur l'illustration.

Définissons également y avec la même chaîne, et z en reprenant la tête de list:

# let y = "hello";;
val y : string = "hello"
# let z = List.hd list ;;
val z : string = "hello"
3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 BLK#2 3.1. Entiers, listes, chaînes String: 5 chars "hello" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 BLK#2 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes String: 5 chars "world" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes Block(0): #2 STR#1 0 3.1. Entiers, listes, chaînes 1 3.1. Entiers, listes, chaînes String: 5 chars "hello" 3.1. Entiers, listes, chaînes String: 1 char "!" 3.1. Entiers, listes, chaînes 0 3.1. Entiers, listes, chaînes list 3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes x 3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes y 3.1. Entiers, listes, chaînes 3.1. Entiers, listes, chaînes z 3.1. Entiers, listes, chaînes

Cette fois, la chaîne n'est pas partagée, puisque la définition de y ne fait pas appel à x ni à la tête de list. Au contraire de z qui, en utilisant cette dernière, se retrouve à pointer sur le même bloc. En conséquence, une modification de la chaîne pointée par y n'aura pas de conséquence sur l'autre chaîne pointée par x, z et la tête de list.

3.2. Types sommes

Définissons un type d'arbre de la façon suivante:

# type 'a tree =
  | Leaf of 'a
  | Node of 'a tree * 'a tree ;;
type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

Nous avons deux constructeurs possédant chacun des arguments. Les valeurs construites avec ces deux constructeurs seront donc représentées par des blocs ayant respectivement les tags 0 et 1. Les valeurs Leaf _ seront dans un bloc avec un champ, pour l'unique argument, et les valeurs Node _ nécessiteront des blocs à deux champs pour représenter les deux arguments.

S'il s'agit d'arbres d'entiers int tree, la valeur des feuilles sera stockée comme un entier directement dans l'unique champ d'un bloc de tag 0 (Leaf). Si c'est par exemple un string tree, ce premier champ contiendra un pointeur vers un bloc contenant la chaîne. Vérifions cela:

# let t = Node (Leaf 1, Leaf 2);;
val t : int tree = Node (Leaf 1, Leaf 2)
# let string_tree = Node (Leaf "hello", Leaf "world!");;
val string_tree : string tree = Node (Leaf "hello", Leaf "world!")
3.2. Types sommes 3.2. Types sommes Block(1): #2 BLK#1 BLK#1 3.2. Types sommes Block(0): #1 1 3.2. Types sommes 0 3.2. Types sommes Block(0): #1 2 3.2. Types sommes 1 3.2. Types sommes Block(1): #2 BLK#1 BLK#1 3.2. Types sommes Block(0): #1 STR#1 3.2. Types sommes 0 3.2. Types sommes Block(0): #1 STR#1 3.2. Types sommes 1 3.2. Types sommes String: 5 chars "hello" 3.2. Types sommes 0 3.2. Types sommes String: 6 chars "world!" 3.2. Types sommes 0 3.2. Types sommes t 3.2. Types sommes 3.2. Types sommes string_tree 3.2. Types sommes

Définissons un autre arbre, utilisant le premier arbre d'entiers t pour mettre en évidence le partage des représentations:

# let t2 = Node (t, Node (Node (Leaf 3, Leaf 4), Leaf 5));;
val t2 : int tree =
  Node (Node (Leaf 1, Leaf 2), Node (Node (Leaf 3, Leaf 4), Leaf 5))
3.2. Types sommes 3.2. Types sommes Block(1): #2 BLK#1 BLK#1 3.2. Types sommes Block(0): #1 1 3.2. Types sommes 0 3.2. Types sommes Block(0): #1 2 3.2. Types sommes 1 3.2. Types sommes Block(1): #2 BLK#2 BLK#2 3.2. Types sommes 0 3.2. Types sommes Block(1): #2 BLK#2 BLK#1 3.2. Types sommes 1 3.2. Types sommes Block(1): #2 BLK#1 BLK#1 3.2. Types sommes 0 3.2. Types sommes Block(0): #1 5 3.2. Types sommes 1 3.2. Types sommes Block(0): #1 3 3.2. Types sommes 0 3.2. Types sommes Block(0): #1 4 3.2. Types sommes 1 3.2. Types sommes t 3.2. Types sommes 3.2. Types sommes t2 3.2. Types sommes
3.3. Exemple de partage: les ensembles

Le module Set est utilisé pour manipuler des ensembles dans un style fonctionnel, c'est-à-dire qu'un ajout renvoie un nouvel ensemble. Construisons des ensembles par ajouts successifs et voyons ce qui reste partagé:

module S = Set.Make(String);;
# let set1 = S.empty ;;
val set1 : S.t = <abstr>
# let set2 = S.add "hello" set1;;
val set2 : S.t = <abstr>
# let set3 = S.add "world" set2;;
val set3 : S.t = <abstr>
# let set4 = S.add "!" set3;;
val set4 : S.t = <abstr>
3.3. Exemple de partage: les ensembles 3.3. Exemple de partage: les ensembles Int: 0 3.3. Exemple de partage: les ensembles Block(0): #4 0 STR#1 0 1 3.3. Exemple de partage: les ensembles String: 5 chars "hello" 3.3. Exemple de partage: les ensembles 1 3.3. Exemple de partage: les ensembles Block(0): #4 0 STR#1 BLK#4 2 3.3. Exemple de partage: les ensembles 1 3.3. Exemple de partage: les ensembles Block(0): #4 0 STR#1 0 1 3.3. Exemple de partage: les ensembles 2 3.3. Exemple de partage: les ensembles String: 5 chars "world" 3.3. Exemple de partage: les ensembles 1 3.3. Exemple de partage: les ensembles Block(0): #4 BLK#4 STR#1 BLK#4 2 3.3. Exemple de partage: les ensembles 1 3.3. Exemple de partage: les ensembles 2 3.3. Exemple de partage: les ensembles Block(0): #4 0 STR#1 0 1 3.3. Exemple de partage: les ensembles 0 3.3. Exemple de partage: les ensembles String: 1 char "!" 3.3. Exemple de partage: les ensembles 1 3.3. Exemple de partage: les ensembles set1 3.3. Exemple de partage: les ensembles 3.3. Exemple de partage: les ensembles set2 3.3. Exemple de partage: les ensembles 3.3. Exemple de partage: les ensembles set3 3.3. Exemple de partage: les ensembles 3.3. Exemple de partage: les ensembles set4 3.3. Exemple de partage: les ensembles

Il apparaît qu'à ce moment, set3 et set4 partagent notamment un noeud de l'arbre utilisé pour représenter un ensemble.

3.4. Modifications

Le type 'a ref est un type enregistrement contenant un seul champ mutable. C'est ce que nous voyons par exemple avec le code suivant:

# let x = ref (Bytes.of_string "bla bla") ;;
val x : bytes ref = {contents = <abstr>}
3.4. Modifications 3.4. Modifications Block(0): #1 STR#1 3.4. Modifications String: 7 chars "bla bla" 3.4. Modifications 0 3.4. Modifications x 3.4. Modifications

Le fait qu'un champ puisse être modifié fait partie du typage, et cela n'apparaît donc plus dans la représentation. Il serait donc tout à fait possible de modifier n'importe quelle valeur, par exemple avec un bout de code en C appelé depuis OCaml.

Définissons maintenant y pour pointer sur la même valeur que x (un enregistrement avec un champ mutable, donc) et z qui pointe sur la valeur pointée par le champ de l'enregistrement x:

# let y = x ;;
val y : bytes ref = {contents = <abstr>}
# let z = !x ;;
val z : bytes = <abstr>
3.4. Modifications 3.4. Modifications Block(0): #1 STR#1 3.4. Modifications String: 7 chars "bla bla" 3.4. Modifications 0 3.4. Modifications x 3.4. Modifications 3.4. Modifications y 3.4. Modifications 3.4. Modifications z 3.4. Modifications

Modifions le tableau d'octets pointé par x, puis modifions x pour le faire pointer sur un autre tableau:

# Bytes.set !x 0 'O';;
- : unit = ()
# x := Bytes.of_string "coucou";;
- : unit = ()
3.4. Modifications 3.4. Modifications Block(0): #1 STR#1 3.4. Modifications String: 6 chars "coucou" 3.4. Modifications 0 3.4. Modifications String: 7 chars "Ola bla" 3.4. Modifications x 3.4. Modifications 3.4. Modifications y 3.4. Modifications 3.4. Modifications z 3.4. Modifications

Nous constatons que le tableau d'octets associé à la variable z a bien été modifié, puis que le champ de l'enregistrement pointe maintenant un autre tableau dans un nouveau bloc.

3.5. Tableaux

Lorsqu'on copie un tableau avec Array.copy, ou un objet avec Oo.copy, il s'agit d'une copie "peu profonde" (shallow copy): les valeurs contenues dans les cases du tableau sont copiées dans un nouveau tableau. Ces valeurs sont soit des entiers soit des pointeurs, ce qui signifie que les valeurs pointées ne sont pas dupliquées mais partagées entre les deux tableaux.

# let t = Array.init 3 (fun i -> string_of_int i);;
val t : string array = [|"0"; "1"; "2"|]
# let t2 = Array.copy t;;
val t2 : string array = [|"0"; "1"; "2"|]
3.5. Tableaux 3.5. Tableaux Block(0): #3 STR#1 STR#1 STR#1 3.5. Tableaux String: 1 char "0" 3.5. Tableaux 0 3.5. Tableaux String: 1 char "1" 3.5. Tableaux 1 3.5. Tableaux String: 1 char "2" 3.5. Tableaux 2 3.5. Tableaux Block(0): #3 STR#1 STR#1 STR#1 3.5. Tableaux 0 3.5. Tableaux 1 3.5. Tableaux 2 3.5. Tableaux t 3.5. Tableaux 3.5. Tableaux t2 3.5. Tableaux