debut.gif (172 octets) boutprec.gif (153 octets) boutsuiv.gif (154 octets)

8. États de mémoire

Au début de ce chapitre nous sommes dotés d'un langage qui permet de faire des choses assez complexes, mais démuni d'une capacité importante : affecter le contenu de la mémoire de l'ordinateur.

Ce chapitre va apporter une réponse à cette attente, mais d'abord un nouveau type de données.

 


8.1 Vecteurs

 

8.1.1 Accéder aux données en temps constant

Nous disposons d'une structure de données qui permet d'agréger ensemble une quantité quelconque de données élémentaires, c'est la liste. Comme nous pouvons construire des listes de listes et que des procédures comme cons et append sont toujours disposées à leur ajouter de nouveaux éléments, nous pouvons penser que cette construction est adaptée à la modélisation des données les plus complexes qui peuvent se présenter à nous. Nous allons voir qu'une limite va se présenter.

Après avoir soigneusement rangé nos données dans une liste, supposons qu'il nous faille accéder à son nième élément (le premier est numéroté 0, un tic d'informaticien) : 


(define (nieme L n)
   (if (zero? n)
       (car L)
       (nieme (cdr L) (- n 1))))

La procédure nieme n'est guère robuste puisqu'elle ne vérifie même pas que la valeur de n n'excède pas la taille de la liste, mais là n'est pas notre propos.

On voit que le programme va invoquer n fois la procédure cdr et construire donc n listes nouvelles. Si n vaut 2 peut importe, mais si nous voulons représenter par des listes une collection de séquences biologiques de quelques milliers de nucléotides sur laquelle nous allons faire quelques millions de comparaisons, notre programme risque d'être d'une « lenteur exécrable » ([Que94] p. 173).

Nous aimerions disposer d'une structure de données analogue à la liste mais où l'accès à l'élément de rang n se fasse dans un temps constant, indépendant de la valeur de n et si possible bref. Nous savons peut-être que la mémoire physique des ordinateurs fonctionne ainsi, alors il n'y a pas de raison pour que notre méta-langage favori ne nous en procure pas une abstraction opératoire. La voici.

 


8.1.2 Le type vecteur en Scheme

Un vecteur est une fonction, au sens mathématique, d'un ensemble index dans le domaine des valeurs licites du langage. L'ensemble index est un sous-ensemble fini des entiers.

En termes moins formels, les vecteurs de Scheme sont des structures de données hétérogènes dont les éléments sont indexés par des entiers consécutifs commençant à 0. À chaque valeur d'indice on sait faire correspondre l'élément correspondant.

La longueur d'un vecteur est le nombre de ses éléments ; c'est un entier non négatif qui est fixé une fois pour toutes à la création du vecteur. Les indices valides pour un vecteur sont les entiers non négatifs inférieurs à sa longueur. Le premier élément est indexé par zéro, et le dernier par la longueur moins un.

La représentation externe utilisée pour noter les vecteurs est :

 

#(objet ...)

Ainsi, voici un vecteur de longueur 3 dont l'élément d'indice 0 est le nombre 4, l'élément d'indice 1 la liste (2 2 2 2) et l'élément d'indice 2 la chaîne "Anna" :

 

#(4 (2 2 2 2) "Anna")

Les vecteurs, pas plus que les listes, ne sont des objets auto-évaluants, pour dénoter un objet-vecteur il faut le quotter :

 

'#(4 (2 2 2 2) "Anna")

(vector? obj)

renvoie #t si obj est un vecteur et #f autrement.

La création d'un vecteur se fait avec make-vector41 ou vector41 :

 

(make-vector k [lest])

renvoie un nouveau vecteur de k éléments éventuellement initialisés à lest8.1 ;

 

(vector objet ...)

retourne un vecteur dont les éléments contiennent les arguments (syntaxe analogue à list).

 

(vector-length vecteur)

retourne le nombre d'éléments de vecteur.

Pour accéder à un élément quelconque, de rang k, d'un vecteur :

 

(vector-ref vecteur k)

vector-ref41 retourne la valeur de l'élément k de vecteur. Attention, l'élément 0 est le premier, l'élément 1 est le second, etc. :

 

: (vector-ref '#(1 1 2 3 5 8 13 21)
              5)
8

Pour modifier un élément quelconque, de rang k, d'un vecteur :

 

(vector-set! vecteur k objet)

vector-set! place la valeur d'objet dans la position k de vecteur.

Cette procédure introduit dans notre langage une possibilité radicalement nouvelle par rapport à ce que nous avons vu jusqu'à présent : elle modifie physiquement le vecteur passé en argument. On dit que les vecteurs sont des objets mutables. vector-set! est un mutateur, et pour le signaler son nom est suffixé d'un point d'exclamation ; la valeur retournée par cette procédure est #unspecified. La section 8.2 ci-dessous élargira cette notion de mutation.

Il est enfin possible de convertir des listes en vecteurs et des vecteurs en listes :

 

(vector->list vecteur)

(list->vector liste)

vector->list retourne une nouvelle liste constituée des objets contenus dans les éléments de vecteur. list->vector retourne un nouveau vecteur initialisé avec les éléments de liste.

Un exemple de programmation avec les vecteurs vient à la fin de ce chapitre.

 


8.2 Environnement et mémoire

 

8.2.1 Affectation

Nous savons définir une variable au Top-level avec define et lui lier une valeur, mais nous ne savons pas modifier sa valeur (sauf si c'est un vecteur) ; si nous écrivons un autre define avec le même nom dans le même environnement, nous définissons une nouvelle variable qui « écrase » la précédente parce qu'elle a le même nom, mais nous ne modifions pas la valeur de la variable précédente.

Nous savons aussi créer des liaisons locales avec let et ses cousins, et nous pouvons ainsi créer des objets homonymes qui se masquent les uns les autres conformément au modèle d'évaluation avec environnement, mais nous ne savons pas modifier la valeur de ces objets. Les seuls objets que nous sachions modifier sont les vecteurs.

Pourtant il existe des cas où il serait utile de pouvoir conserver l'état d'une chose représenté par une variable, et de faire évoluer cet état. Par exemple, si cette chose est un compte bancaire, il serait bon que la variable qui en représente le solde puisse voir sa valeur modifiée au gré des dépôts et des retraits représentés par des procédures nommées verser et retirer, selon le modèle ci-dessous :

 

: (verser 1000)
1000

: (retirer 300)         ;; 92 $[\mathcal{A}]$97
700

: (retirer 300)         ;; 92 $[\mathcal{B}]$97
400

: (retirer 500)
solde insuffisant !

Les programmes dont nous avons écrit le comportement souhaité, mais pas la définition, retournent comme valeur le solde du compte après les opérations.

Remarquons une chose importante : toutes les expressions que nous avions vues jusqu'à présent retournaient la même valeur chaque fois qu'on les évaluait. Ce comportement était celui d'une fonction mathématique. La comparaison des lignes $[\mathcal{A}]$ et $[\mathcal{B}]$ nous montre qu'ici il n'en est rien. Adjoindre au langage ce que nous souhaitions introduira la notion d'état de la mémoire, et éloignera Scheme de la notion de fonction mathématique. C'est le prix à payer pour l'introduction des états et de l'affectation.

Le solde est représenté par une variable solde dont il faut bien modifier la valeur si nous ne voulons pas que notre banque fasse faillite. C'est la forme spéciale set! qui nous permet cette modification. Voici sa syntaxe :

 

(set! variable expression)

L'évaluation d'une telle expression a pour effet de modifier la valeur de la variable dans l'environnement courant en lui liant la valeur de l'expression. La valeur retournée est #unspecified ; c'est donc un effet de bord, l'effet de bord par excellence. La variable doit avoir été créée au préalable (par define ou let par exemple).

L'opération définie par set! s'appelle l'affectation.

Il est d'usage en Scheme que les formes spéciales et les procédures qui modifient les valeurs d'objets reçoivent un nom terminé par un point d'exclamation.

Notre programme de gestion bancaire s'écrit désormais ainsi : 


(define solde 0)

(define (retirer somme)
   (if (< solde somme)
       "solde insuffisant !"
       (begin
          (set! solde (- solde somme))
          (display solde))))

(define (verser somme)
   (begin
      (set! solde (+ somme solde))
      (display solde)))

C'est indubitablement rudimentaire, mais nous l'améliorerons.

 


8.2.2 Encapsulation et passage de message

Munis de l'affectation, nous pouvons envisager de nouveaux projets ; par exemple nous souhaitons qu'une de nos procédures tienne le compte du nombre de fois où elle est exécutée en modifiant un compteur par une procédure adéquate : 


(define compteur 0)          ; \label{incfauxa}

(define (incrementer! x)     ; \label{incfauxb}
   (set! x (+ x 1)))         ; \label{incfauxc}

(define (carre x)
   (begin
      (incrementer! compteur) ; \label{incfauxd}
      (* x x)))

: (carre 5)
25

: compteur
0

Pourquoi échouons-nous ? Parce que le passage des arguments en Scheme a lieu par valeur. Lorsqu'en $[\mathcal{F}]$ carre appelle incrementer!, une liaison est créée pour la durée de l'exécution d'incrementer! entre son paramètre formel x et la valeur de compteur, mais la variable globale compteur définie en $[\mathcal{C}]$ n'est en rien modifiée par l'affectation $[\mathcal{E}]$.

Cet échec nous conduit à chercher un autre moyen pour modifier des variables, on dit aussi les muter. Dans la terminologie Scheme, la mutation d'un objet désigne une modification physique.

Nous allons pour ce faire utiliser une caractéristique des $\lambda$-expressions, leur implantation dans des fermetures où elles sont accompagnées d'un pointeur vers leur environnement de définition. Si nous établissons une liaison dans cet environnement de définition, n'y restera-t-elle pas durablement ? Et si nous programmons la $\lambda$-expression de telle sorte qu'en fonction des arguments que nous lui donnons elle modifie ou renvoie la valeur de cette liaison, n'aurons-nous pas atteint notre but ? 


(define compteur
  (let ((val 0))
    (lambda message
      (case (car message)
        ((val) val)
        ((inc) (set! val (+ 1 val))  ; \label{incbona}
               val)))))

: (compteur 'val)
0

(define (carre x)
   (begin
      (compteur 'inc)
      (* x x)))

: (carre 7)
49

: (compteur 'val)                     ; \label{incbonb}
1

[ Nous introduisons au passage la forme spéciale case, une extension de if dont on trouvera la description autorisée dans [CKR98].] 8.2

Maintenant notre affaire marche, parce que la forme set! de la ligne $[\mathcal{G}]$ modifie la valeur d'une variable de l'environnement de définition de la $\lambda$-expression, et non pas d'un paramètre. Cette modification reste précieusement enregistrée dans la fermeture, et l'interrogation de la ligne $[\mathcal{H}]$ nous en restitue le résultat.

Cette façon de programmer s'appelle programmation par passage de message, les « messages » sont ici par exemple 'inc et 'val. Ce n'est pas encore de la programmation par objets, mais cela s'en approche. La valeur du compteur est dite encapsulée dans une $\lambda$-expression.

Dégrisés après l'ivresse du succès, nous pouvons nous dire que définir un seul compteur de cette façon est un peu mesquin alors qu'il serait si simple et plus dans l'esprit de la programmation de définir un générateur de compteurs : 


(define (make-compteur val)              ; \label{mkctra}
   (lambda message
      (case (car message)
         ((val) val)
         ((inc) (set! val (+ 1 val))
                val))))

(define compteur-carre (make-compteur 0)) ; \label{mkctrb}

: (compteur-carre 'val)
0

(define (carre x)
   (begin
      (compteur-carre 'inc)
      (* x x)))

: (carre 7)
49

: (compteur-carre 'val)
1

Nous pouvons même choisir la valeur initiale de chaque compteur que nous créons. La ligne $[\mathcal{I}]$ définit une procédure dont l'appel, ligne $[\mathcal{J}]$, renvoie une $\lambda$-expression (ici nommée compteur-carre) qui contient dans son environnement de définition la liaison d'une variable val. Ensuite nous interrogeons ou mutons cette variable en envoyant des messages adéquats à la $\lambda$-expression compteur-carre.

 

8.2.3 Sous l'environnement, la mémoire

L'affectation représentée en Scheme par la forme spéciale set! que les Lispiens utilisent le moins possible pour éviter de perdre l'aspect fonctionnel de leur langage est en fait l'instruction fondamentale des langages impératifs, pour ne pas dire leur instruction unique. L'affectation modifie l'état de la mémoire, c'est l'action de base du calcul selon l'architecture de von Neumann.

En Scheme la mémoire et ses états nous sont la plupart du temps cachés par un niveau d'abstraction plus élevé, l'environnement. Mais il est bon d'avoir une idée des choses plus concrètes qui se cachent sous nos confortables abstractions. Une idée, c'est à dire un modèle de leur fonctionnement.

Nous avons dit jusqu'à présent (section 2.4 page [*]) qu'à une variable correspondait un liaison dans l'environnement courant, qui permettait de lui associer une valeur. Nous précisons maintenant que cette valeur réside dans la mémoire.

À quoi ressemble la mémoire d'un ordinateur ? Très précisément à un vecteur. Et pour cause, le vecteur a été conçu à l'image de la mémoire.

Comment retrouver une valeur dans la mémoire ? Comme dans un vecteur, par un numéro d'élément. Les éléments de la mémoire sont souvent nommés cases (ou places), nous dirons que nous repérons l'emplacement d'une donnée par son numéro de case mémoire.

La nature des liaisons fournies par l'environnement peut maintenant être précisée : l'environnement est une fonction qui à une variable fait correspondre un numéro de case mémoire.

Dans cette case mémoire il y a la valeur : la mémoire est une fonction qui à un numéro de case fait correspondre la valeur contenue par la case.

La valeur d'une variable x est le résultat de la composition de ces deux fonctions :

 

(mémoire (environnement x)) : x \(\to\)  valeur de x

 

 

Figure: Mémoire et environnement
\includegraphics[scale=0.8]{../Images/Memoire/memoire-env.epsi}67

 

Les procédures et les formes terminées par un point d'exclamation ainsi que define modifient la mémoire. Les lieurs comme let et l'appel de procédure réalisent des changements d'environnement.

Pour illustrer la différence entre ces deux notions, prenons un exemple : 


(let ((n 10))
   (let ((proc (lambda (i) (* i n))))
      (proc 2)))
20

Nous avions vu que la fermeture de proc pouvait se représenter ainsi :

 

 

Figure 8.2: Fermeture
\includegraphics[scale=0.8]{../Images/Memoire/fermeture2.epsi}67

 

Nous avions aussi vu qu'une modification de l'environnement du let le plus interne ne modifiait pas l'environnement de proc dont le comportement restait identique : 


(let ((n 10))
   (let ((n 0)
         (proc (lambda (i) (* i n))))
      (proc 2)))
20

et l'alinéa 7.2.2 page [*] avait expliqué pourquoi.

Modifions maintenant le programme en y introduisant une affectation : 


(let ((n 10))
   (let ((proc (lambda (i) (* i n))))
      (set! n 3)                ;      \label{letca}
      (proc 2)))
6

L'affectation de la ligne [*] a modifié la mémoire, donc l'environnement ne fournit plus la même valeur de n à proc, et son comportement est modifié. Le problème demande d'ailleurs une analyse subtile, parce que : 


(let ((n 10))
   (let ((n 0)
         (proc (lambda (i) (* i n))))
      (set! n 3)                ;      \label{letda}
      (proc 2)))
20

L'affectation de la ligne [*] modifie le contenu de la case mémoire qui contient la valeur du premier n trouvé, et là ce n'est pas le même qu'en [*] ! Les leçons de ces avatars de proc sont énoncées ci-dessous à l'alinéa 8.2.4.

 


8.2.4 Conseils de programmation

Quatre mises en garde :

 

Deux recommandations :

 

 


8.3 Chirurgie des listes

Comme tout objet, un doublet peut-être affecté par set!, ce qui revient à modifier la valeur du pointeur qui pointe vers son car pour le faire pointer vers autre chose, pas forcément un doublet d'ailleurs. Mais comme un doublet consiste lui-même en deux pointeurs, Scheme comporte des procédures pour faire pointer l'un ou l'autre de ces deux pointeurs vers ailleurs, ce qui revient à modifier physiquement la consistance du doublet (ou de la liste, qui n'est qu'une variété de doublet). Ces opérations de découpage corporel s'appellent set-car! et set-cdr!. La tradition de Scheme les regarde avec une certaine méfiance.

 

 

Figure: set-car! et set-cdr!
\includegraphics[scale=0.8]{../Images/Memoire/chirurgie.epsi}67

 

On remarque le caractère brutal de l'amputation réalisée par set-cdr!, qui commande de l'employer avec cautèle et parcimonie.

Il faut bien saisir la différence de nature entre le couple set-car! - set-cdr! et les autres procédures de traitement de listes : cons, car et cdr permettent de construire des listes ou d'en extraire des parties, alors que set-car! et set-cdr! modifient la structure d'une liste. cons renvoie comme résultat une nouvelle liste alors que set-car! et set-cdr! renvoient un résultat #unspecified et agissent par effet de bord, en détruisant éventuellement la liste traitée.

 

 

Figure: Manipulation avec set-car!
\includegraphics[scale=0.8]{../Images/Memoire/chirurgie2.epsi}67

 

 


8.4 Un usage des vecteurs : annuaire électronique

Le développement de cet exemple sera l'occasion d'introduire une structure de données nouvelle, utilisant l'adressage dispersé.

L'objectif de l'adressage dispersé (encore appelé adressage associatif, en anglais hash-coding)44 est de bénéficier des avantages à la fois des types fluides comme les listes et des types rigides comme les vecteurs.

Les structures de données à adressage dispersé s'appellent au choix tables à adressage dispersé, tables associatives, tables de hachage, hash-tables, mémoires associatives .

 


8.4.1 Le problème et sa solution naïve

Supposons que nous ayons à écrire un programme destiné à répondre à des interrogations de l'annuaire électronique interne de l'Université de Paizay-le-Tort. Il faut aussi pouvoir introduire dans l'annuaire les informations relatives aux nouveaux abonnés.

Pour améliorer le temps de réponse aux interrogations, ce programme gardera en mémoire l'ensemble de l'annuaire. La première idée qui vient à l'esprit sera de construire une liste d'associations telle que nous avons décrit cette structure de données en 6.5 page [*] : chaque personne identifiée dans l'annuaire sera représentée par un doublet dont le car sera une chaîne de caractères donnant son nom et le cdr son numéro de téléphone.

Au chapitre suivant nous connaîtrons assez les entrées-sorties pour constituer cette liste d'associations à partir d'un fichier externe, mais pour les besoins du prototype nous entrerons les données à la main :

Un générateur d'annuaire naïf

(define (make-annuaire)
  (let ((un-annuaire '()))
    (lambda message
      (case (car message)
        ((peupler)
          (letrec ((
            boucle 
              (lambda ()
                (display "Entrez nom et numéro : ")
                (let ((nom (read))
                      (numero (read)))
                   (if (string=? nom "")
                       #f
                       (begin
                          (set! un-annuaire       ; \label{lisp:annaif}
                               (cons (cons nom numero) un-annuaire))
                         (boucle)))))))
            (boucle)))
        ((interrogation)
          (let* ((nom (cadr message))
                 (reponse (assoc nom un-annuaire)))
              (if reponse
                 (cdr reponse)
                 "Pas d'abonné au numéro demandé")))
        ((afficher)
           (print un-annuaire))))))

74

 

(define cet-annuaire (make-annuaire))

(cet-annuaire 'peupler)
Entrez nom et numéro : "Raoul" "18"
Entrez nom et numéro : "Valérie" "14"
Entrez nom et numéro : "" ""
#f

(cet-annuaire 'afficher)
Valérie 14
Raoul 18
Paul 6
Dupont 4
#f

Ce programme naïf donnera peut-être satisfaction si l'Université de Paizay-le-Tort est petite, mais si ses effectifs sont importants l'usage direct des listes d'associations aura vite deux inconvénients :

 

Comment surmonter ces inconvénients ?

 

8.4.2 Des alternatives, mais avec leurs défauts

Nous échapperions aux inconvénients signalés ci-dessus en choisissant pour l'annuaire une structure de données à temps d'accès constant, indépendant de la position de l'élément à atteindre, et mutable élément par élément. Nous connaissons une telle structure de données, c'est le vecteur.

Nous pouvons imaginer représenter l'annuaire par un vecteur de doublets, chaque doublet contenant un couple nom-numéro de téléphone.

Cette idée soulève plusieurs problèmes : d'abord les vecteurs ont une taille fixe. Il faudrait donc créer un vecteur d'une taille fixée à l'avance telle qu'elle dépasse le nombre d'entrées présent et à venir de l'annuaire. Ce n'est pas satisfaisant pour l'esprit.

Ensuite il faut définir une procédure pour jouer le rôle d'assoc, qui en fonction d'un nom retrouvera la bonne entrée pour nous délivrer le numéro de téléphone correspondant :

 

Comment faire ?

 


8.4.3 L'adressage dispersé

La solution que nous cherchons doit combiner tous les avantages de celles que nous avons envisagées, et en éviter les inconvénients.

Soit pour représenter notre annuaire un vecteur de taille n. Pour insérer à sa place chaque doublet représentatif d'un couple nom-numéro, nous allons essayer de construire une fonction f qui à un nom fasse correspondre un entier compris entre 0 et n-1. Le nom est utilisé comme clé d'accès à la table. Pour une valeur c de la clé, l'entrée de l'annuaire sera rangée dans l'élément du vecteur de rang i = f(c) (on dit aussi alvéole).

Cette fonction permettra également de retrouver le doublet à chaque interrogation, et ce en un laps de temps constant, égal au temps de calcul de la fonction plus le temps d'accès à un élément de vecteur.

La fonction f s'appelle la fonction d'association, ou d'adressage dispersé, ou de dispersion, ou de hachage, ou de hash-coding44 .

L'idéal serait que la fonction f soit injective, c'est à dire que chaque valeur de i corresponde à une seule valeur possible de c. Ce n'est pas possible, ne serait-ce que parce que la variété des patronymes possibles est trop grande.

Plusieurs valeurs de c peuvent donc donner par f la même valeur de i, c'est ce que l'on appelle une collision, ou une synonymie. En cas de collision, un doublet va vouloir se ranger dans un élément de vecteur déjà occupé. Afin de faire face à cette situation inévitable, chaque élément de vecteur ne sera pas un doublet, mais une liste associative semblable à celle de la solution naïve de la section 8.4.1.

Cette proposition semble absurde : elle réintroduit la solution dont nous ne voulions plus.

En fait c'est sensé : le parcours de liste de l'alinéa 8.4.1 était une mauvaise solution parce que la liste était potentiellement longue.

Ici nous allons choisir une fonction f telle que chaque indice i corresponde à un ensemble de clés $\{c_{i1}, c_{i2}, \ldots c_{ij} \ldots, c_{ip}\}$ d'effectifs sensiblement voisins ; s'il y a N individus dans notre annuaire, la longueur de chaque liste sera de l'ordre de N/n. Le choix judicieux de n et de f devrait assurer une efficacité raisonnable à l'algorithme.

 

 

Figure: Adressage dispersé
\includegraphics[scale=0.8]{../Images/Memoire/hash.epsi}67

 

Le choix d'une fonction d'adressage a des conséquences lourdes sur les performances de l'algorithme (voir [ASU86] page 478 pour une introduction, ainsi que [CLR94], [Knu68] et [KGP89]).8.3Nous allons en choisir une très simple qui suffira à notre exemple. À chaque caractère correspond une valeur entière appelée son code ASCII, donnée par la procédure Scheme char->integer :

 

1:=> (char->integer #\a)
97

1:=> (char->integer #\A)
65

1:=> (char->integer #\é)
233

La somme des codes ASCII des caractères d'une chaîne se calcule simplement :

 

1:=> (apply + (map char->integer (string->list "Aéa")))
395

Ce nombre n'est pas compris entre 0 et n-1, mais le reste de sa division par n l'est. [ASU86] suggère que le choix d'une valeur première pour n améliore l'uniformité de la répartition des valeurs sur l'intervalle $\lbrack 0, n-1 \rbrack $. [CLR94] recommande en outre que ce nombre premier ne soit pas proche d'une puissance de 2. Pour n = 23 :

 

(remainder (apply + (map char->integer (string->list "Aéa")))  23)
4

Cette fonction rudimentaire fera l'affaire en première approche.

Le programme de la solution naïve doit être modifié ainsi :

Générateur d'annuaire moins naïf

(define (make-annuaire)
  (let* ((n 23) ; nombre d'éléments du vecteur
         (un-annuaire (make-vector n '())))
    (lambda message
      (case (car message)
        ((peupler)
          (letrec 
            ((boucle 
               (lambda ()
                 (display "Entrez nom et numéro : ")
                 (let ((le-nom (read))
                       (numero (read)))
                   (if (not (string=? le-nom ""))
                       (begin
                         (vec!:ajouter le-nom 
                                       numero 
                                       un-annuaire)
                         (boucle)))))))
            (boucle)))
        ((interrogation)                      ; \label{lisp:annruse}
          (let* ((le-nom (cadr message))
                 (la-case (hash le-nom n))
                 (reponse 
                    (assoc le-nom (vector-ref 
                             un-annuaire la-case))))
            (if reponse
               (cdr reponse)
               "Pas d'abonné au numéro demandé")))
        ((donner)
           un-annuaire)
        ((afficher)
         (for-each-vector print un-annuaire))))))

74

Fonction d'association (« hash »)

(define (hash nom taille-table) 
    (remainder 
      (apply + (map char->integer (string->list nom)))
      taille-table))

74

... ses programmes auxiliaires

(define (assoc!:ajouter nom numero liste)
  (cons (cons nom numero) liste))

(define (vec!:ajouter nom numero vecteur)
  (let* ((n (vector-length vecteur))
         (une-case (hash nom n))
         (elem (vector-ref vecteur une-case)))
    (vector-set! vecteur une-case
                 (assoc!:ajouter nom numero elem))))

74

... et encore un

(define (for-each-vector proc V)
  (let ((longueur (vector-length V)))
    (letrec ((boucle 
               (lambda (index)
                 (if (not (= index longueur))
                   (begin
                    (proc (vector-ref V index))
                    (boucle (+ index 1)))))))
    (boucle 0))))

74

Ce programme-jouet n'a pour but que d'illustrer le cours, il lui manque des traitements essentiels : contrôle de la correction des entrées, supression d'entrées, détection de doublons, et autres fonctions dont l'ajout est laissé au lecteur pour son amusement.

Au fil de cet exercice il se sera convaincu que le temps de recherche moyen d'un élément dans une table raisonnablement bien dispersée est proportionnel à N/n, et qu'un des grands avantages de la méthode est qu'il n'y a pas de limite rigide à N, sauf celle de la mémoire dont nous disposons.

[Que94] n'hésite pas à écrire en sa page 118 à propos des tables à adressage dispersé que « leur invention est ... l'une des plus immenses découvertes jamais faites en informatique » : la rédaction de programmes qui en implantent pénètrera sans doute le lecteur de cette conviction.

 


8.5 Gestion de la mémoire physique : GC et pile

 

8.5.1 Le glaneur de cellules

 

8.5.1.1 Remplissage progressif de la mémoire

Fréquemment dans le cours de cet exposé, et surtout à propos des listes, nous évoquons des procédures qui créent un nouvel objet (une liste ou une chaîne) à partir d'un ancien. Le plus souvent nous ne nous intéressons plus ensuite qu'au nouvel objet, et oublions totalement l'objet à partir duquel il a été créé. Ainsi en ligne [*] du programme 8.4.1 :

 

(set! un-annuaire (cons (cons nom numero) un-annuaire))

le cons le plus externe créée une nouvelle liste qui sera liée par set! au symbole un-annuaire. La liste liée précédemment à un-annuaire n'est plus liée à aucun symbole, on dit qu'elle n'est plus référencée, il n'y a plus aucun moyen d'y accéder, elle ne sert plus à rien. Pourtant elle existe toujours et occupe de la place en mémoire. Certes, les éléments de l'ancienne liste un-annuaire n'ont pas été recopiés, ils constituent désormais le cdr du nouvel un-annuaire. Ce qui n'est plus référencé, ce sont les pointeurs qui donnaient accès à l'ancienne liste.

Comme cet appel à cons est dans la procédure interne boucle, appelée comme son nom l'indique pour chaque ajout d'une personne dans l'annuaire, si nous ajoutons 1000 personnes dans l'annuaire nous aurons créé 1000 listes non référencées, ce qui semble à tout le moins inélégant.

Il existe des situations où non seulement les pointeurs vers le car et le cdr d'une liste, mais les éléments eux-mêmes sont abandonnés : la figure 8.4 page [*] section 8.3 en propose un exemple avec set-car!.

Certains processus itératifs peuvent exécuter des millions d'itérations, si chacune crée des objets destinés à être abandonnés à la suivante, les objets abandonnés risquent de saturer la mémoire et de provoquer l'échec du programme.

 

8.5.1.2 Récupérer les cases mémoire inutilisées

Scheme résout ce problème par l'exécution d'une procédure interne du système de programmation nommée glaneur de cellules ou ramasse-miettes (en anglais garbage collector, ou GC). Le mot cellule doit être entendu ici au sens de case mémoire. Le GC est exécuté chaque fois qu'une allocation de mémoire est demandée au système.

L'idée du glanage de cellules part de la constatation qu'à un instant donné de l'exécution d'un programme les seules valeurs contenues par la mémoire susceptibles d'avoir un effet sur le futur des calculs sont celles qui sont référencées, c'est à dire soit liées à une variable, soit accessibles par une succession de car et de cdr ou d'un autre sélecteur.

Si l'on trouve une méthode capable de trier les cases mémoire en deux tas, un pour celles qui sont référencées et dont il faut garder précieusement le contenu, un pour celles qui ne sont pas référencées et qui peuvent donc être réutilisées, nous devrions être à l'abri des saturations de mémoire, du moins de celles qui ne découlent pas de nos algorithmes.

Une telle méthode devra comporter au moins un algorithme de parcours de l'ensemble des cases mémoire référencées. Un tel algorithme doit généralement disposer de racines, c'est à dire d'un ensemble d'adresses de cases mémoire contenant soit des données soit des pointeurs vers des données, récursivement. L'ensemble des racines doit permettre un parcours exhaustif des cases mémoires référencées. La détermination des racines dépend des caractéristiques techniques internes du système de programmation (l'étiquetage des pointeurs ou l'exploration de la pile d'exécution et des tables de variables sont parmi les techniques possibles, les alinéas suivants exposent les notions qui leur correspondent).

 

8.5.1.3

Les méthodes de glanage de cellules se répartissent grosso modo en deux familles : marquage et balayage (mark and sweep) et recopie (stop and copy).

 

8.5.2 Notion d'adresse

Sans entrer dans les détails techniques de réalisation, il convient de donner un aperçu de la gestion de mémoire physique sous-jacente aux abstractions que nous utilisons pour accéder aux objets. Cet alinéa ne s'adresse qu'au lecteur curieux, celui qui le serait moins, ou pris par le temps, peut en remettre la lecture à plus tard.

Tous les objets et mécanismes décrits dans cette section 8.5 sont dissimulés au programmeur Scheme, ce sont des mécanismes de bas niveau. Il est possible de programmer en en ignorant tout, mais avoir la notion de leur existence et une idée de leur fonctionnement ne peut pas nuire.

Pour accéder à un objet nous nous adressons en Scheme à un système de programmation. Le système de programmation a notamment pour fonction de traduire nos expressions Scheme en langage machine. Une correspondance doit être établie entre les références que nos expressions font à des objets et les emplacements physiques attribués à ces objets dans la mémoire de l'ordinateur.

L'emplacement physique attribué à un objet dans la mémoire est repéré par son adresse, qui est généralement le numéro d'ordre de la case mémoire correspondante par rapport au début de la mémoire (adresse 0).

La correspondance entre objet et adresse peut être directe : la valeur de l'objet Scheme est placée dans une case mémoire et le nom de l'objet est traduit par l'adresse de la case. Toute référence à l'objet sera traduite par cette adresse. C'est généralement ce qui se passe pour les objets scalaires de petite taille, comme les entiers, qui sont logés dans une unique case de mémoire appelée mot mémoire.

 

 

Figure 8.6: Adressage direct
\includegraphics[scale=0.8]{../Images/Memoire/adressage-direct.epsi}67

 

Dans le cas d'objets de plus grande taille, comme ceux des types structurés, la correspondance entre objet et adresse est généralement indirecte : le nom de l'objet est traduit par l'adresse d'une case mémoire qui contient non pas sa valeur, mais l'adresse d'une case qui correspond au début de la structure de données.

 

 

Figure 8.7: Adressage indirect
\includegraphics[scale=0.8]{../Images/Memoire/adressage-indirect.epsi}67

 

Ainsi dans l'exemple de la figure 8.7 le nom du vecteur v est traduit par la fonction environnement en l'adresse de la case 1008, qui contient en fait l'adresse de la case 2040 qui contient la valeur de l'élément de rang 0 du vecteur v. Les cases suivantes contiennent les valeurs des éléments suivants du vecteur.

Un objet dont la valeur est une adresse s'appelle un pointeur. Les pointeurs de la représentation des doublets par « boîtes et pointeurs » introduite en section 6.1.1.2 page [*] sont, dans leur réalisation technique, de tels objets.

Scheme emploie les pointeurs de façon implicite, le programmeur peut ignorer jusqu'à leur existence.

 


8.5.3 Pile d'exécution

Chaque fois que nous appliquons une procédure Scheme à des arguments nous construisons un nouvel environnement, qui va contenir notamment les liaisons des paramètres formels avec les valeurs des arguments et celles correspondant aux objets locaux, créés par let par exemple. Ce nouvel environnement vient en fait ajouter des liaisons à l'environnement pré-existant selon le mécanisme décrit en 7.2.2 page [*] et 7.2.3. Lorsque la procédure appelée se termine et renvoie une valeur à son appelant, son environnement d'exécution doit être détruit.

À cet environnement d'exécution il va falloir faire correspondre des emplacements en mémoire qui vont contenir les valeurs des objets.

Lors d'une succession d'appels récursifs, comme en 5.3.2 page [*], il va falloir créer des environnements successifs jusqu'au moment où la récursion aura atteint le cas de base, puis les détruire au fur et à mesure que les évaluations partielles renverront leurs valeurs :

 

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)

L'évolution du contenu de la mémoire lors de l'exécution d'un tel appel est gérée selon une structure de données appelée pile (stack en anglais) : les environnements d'exécution successifs, au fur et à mesure de leur création, vont être empilés comme des assiettes, puis dépilés au fur et à mesure de leur destruction :

 

 

Figure 8.8: Empilement des environnements
\includegraphics[scale=0.8]{../Images/Memoire/pile-env.epsi}67

 

De façon plus générale, la mémoire d'un ordinateur moderne est gérée ainsi : une pile d'exécution reçoit les données nécessaires à l'exécution d'un processus qui démarre, lorsque le processus se termine ses données sont dépilées.

Les données empilées sont les données elles-mêmes dans le cas de données scalaires telles que les entiers, ou des pointeurs sur les données dans le cas de données structurées comme les listes ou les vecteurs.

Les données structurées allouées dynamiquement (par exemple une liste créée par cons), référencées par des pointeurs de la pile, sont créées ailleurs que sur la pile, dans une zone de mémoire appelée le tas (heap en anglais). Nous pouvons préciser la représentation de la figure 8.7, qui devient ci-dessous la figure 8.9.

L'idée de créer sur la pile des données pour une procédure qui démarre et de les dépiler lorsqu'elle se termine paraît simple. Signalons que pour les données structurées créées sur le tas la chose est moins simple, car une même donnée peut être référencée par plusieurs pointeurs. Il est compliqué de savoir à partir de quand une donnée créée sur le tas peut être détruite, et la réponse à cette question compliquée est donnée par le glaneur de cellules.

 

 

Figure 8.9: Adressage indirect, via la pile
\includegraphics[scale=0.8]{../Images/Memoire/pile-tas.epsi}67

 

debut.gif (172 octets) boutprec.gif (153 octets) boutsuiv.gif (154 octets)