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

6. Construire des données

Nous disposons maintenant de moyens suffisants pour réaliser des processus de calcul aussi complexes que nous le désirons, en théorie du moins, parce que la construction efficace et sûre de grands programmes exige dans les faits des outils destinés à organiser l'information qui, s'ils ne changent rien aux grands principes, apportent des améliorations décisives aux conditions de la pratique. Nous introduirons ultérieurement certains de ces outils.

Mais la principale lacune que ce chapitre va commencer à combler concerne les types de données que nous pouvons utiliser : nous savons surtout traiter les nombres. Il en va de l'informatique comme de l'écriture : les Égyptiens et les Sumériens ont inventé l'écriture pour noter des nombres et faire de la comptabilité, mais très vite ils lui ont trouvé des usages plus intéressants. Les premiers ordinateurs étaient vus comme des machines à calculer, mais il est probable que cet usage est aujourd'hui minoritaire.

En fait nous avons déjà introduit des objets autres que les nombres, mais nous ne savons en faire que des usages très restreints. Nous savons utiliser les booléens dans des formes spéciales if, les chaînes de caractères pour retourner des messages d'erreur, les symboles pour désigner des objets. Nous savons aussi combiner des expressions simples en expressions composées, nommément des listes, et nous savons les utiliser pour appeler des procédures.

Le présent chapitre est destiné à enrichir notre collection d'outils qui nous permettront de décrire des données plus complexes.

 


6.1 Doublets

 

6.1.1 Définition et représentation

 

6.1.1.1 Définition

La façon la plus simple de construire un objet composé consiste à unir deux objets élémentaires : l'objet ainsi obtenu s'appelle un doublet ou une paire.

Pour construire un doublet Scheme offre la procédure primitive cons. Cette procédure prend deux arguments et retourne le doublet constitué de leur réunion. Pour accéder aux éléments constitutifs d'un doublet ainsi construit, nous disposons des deux procédures primitives car et cdr, qui acceptent un argument de type doublet et renvoient les éléments qui étaient, respectivement, le premier et le second arguments du cons constructeur.

 

: (define a (cons 1 2))

: (car a)
1

: (cdr a)
2

Plus généralement :

 

: (car (cons 'x 'y))
x

: (cdr (cons 'x 'y))
y

Munis du constructeur cons, nous pouvons créer des doublets dont les éléments constitutifs sont eux-mêmes des doublets :

 

: (define b (cons 3 4))

: (define a-et-b (cons a b))

: (car (car a-et-b))
1

: (car (cdr a-et-b))
3

Nous verrons que cette possibilité de construire des assemblages de doublets permet de réaliser des structures de données suffisamment complexes pour modéliser toutes sortes de problèmes et d'abstractions, depuis la syntaxe d'un langage jusqu'à la structure d'une protéine.

On peut cons-er autre chose que des nombres :

 

: (define capitaine-age (cons "Haddock" 50))

: (define moussaillon-age (cons "Tintin" 22))

et notamment des doublets :

 

: (define equipage (cons capitaine-age moussaillon-age))

: (define les-ages
    (cons (cdr (car equipage))
          (cdr (cdr equipage))))

: (define age-du-capitaine (car les-ages))

: age-du-capitaine
50

Mais on ne peut pas prendre le car ou le cdr d'autre chose que d'un doublet :

 

: (car age-du-capitaine)
*** ERROR - PAIR expected

: (cdr (cdr les-ages))
*** ERROR - PAIR expected

La possibilité de construire avec cons des doublets dont les éléments sont eux-mêmes des doublets confère à cette construction très simple un pouvoir considérable d'élaboration de structures de données très complexes.

 


6.1.1.2 Représentation des doublets par « boîtes et pointeurs »

Nous allons maintenant introduire un moyen graphique de représenter de telles structures, la représentation « boîtes et pointeurs ». Ces termes ne sont pas seulement des métaphores pédagogiques, le terme de pointeur désigne un objet dont la valeur est un moyen d'accès à la valeur d'un autre objet (son adresse par exemple), et la « boîte » évoque la case mémoire qui contient la valeur d'un objet.

 

 

Figure: Boîtes et pointeurs
\includegraphics[scale=0.8]{../Images/Const-listes/boites-pointeurs.epsi}67

 

La règle pour dessiner la figure « boîtes et pointeurs » qui correspond à une expression Scheme constituée de doublets est la suivante :

 

1.
un doublet construit par cons (ou autrement d'ailleurs) est représenté par une boîte double ;
2.
la partie gauche d'une boîte double contient un pointeur vers la boîte qui représente le premier opérande du cons (le car du doublet) ;
3.
la partie droite d'une boîte double contient un pointeur vers la boîte qui représente le second opérande du cons (le cdr du doublet) ;
4.
si l'opérande est lui-même une expression dont l'opérateur est cons, il est représenté par une boîte double, retour à 2 ;
5.
si l'opérande est une expression primitive sa représentation est placée dans une boîte simple qui ne contient aucun pointeur.

Cette règle envisage tous les cas possibles pour l'instant.

La structure représentée dans la partie droite de la figure 6.1 ci-dessus illustre un moyen de réunir au nom du capitaine Haddock l'information relative à son âge et au bateau de 40 tonneaux qu'il commande : 


(define un-capitaine
  (cons
    (cons "Haddock"
          (cons "Astrolabe" "40 t"))
    "50 ans"))

 

6.1.2 Utilisation des doublets, constructeurs, sélecteurs

La définition d'une structure de données telle que celle donnée en $[\mathcal{A}]$ et illustrée par la figure 6.1 peut servir à organiser des informations complexes de manière à en faciliter le traitement. On imagine que l'usage commode d'une telle organisation est gêné par l'enchaînement complexe des cons, car et cdr ; pour s'affranchir de cette difficulté, il convient de se hausser d'un niveau dans l'abstraction en inscrivant ces combinaisons une fois pour toutes dans des procédures auxquelles nous donnerons des noms suggestifs.

Pour créer des exemplaires de la structure de données qui contient les informations relatives à un capitaine et au bateau qu'il commande, nous définissons la procédure suivante (une telle procédure s'appelle un constructeur) :

 

(define (make-capitaine nom age bateau tonnage)  ;; 92 $[\mathcal{B}]$97
    (cons
      (cons nom (cons bateau tonnage))
      age))

Utilisation du constructeur pour créer un exemplaire de la structure avec les paramètres désirés :

 

: (define un-capitaine
     (make-capitaine "Haddock" "50 ans" "Astrolabe" "40 t"))

Définition de la procédure qui permet d'accéder à l'élément de la structure correspondant au nom du capitaine (une telle procédure s'appelle un sélecteur ou un accesseur) :

 

: (define (nom-capitaine ce-capitaine)
    (car (car ce-capitaine)))

Sélecteur pour accéder à l'âge du capitaine :

 

: (define (age-capitaine ce-capitaine)
    (cdr ce-capitaine))

: (age-capitaine un-capitaine)
"50 ans"

: (nom-capitaine un-capitaine)
"Haddock"

Ce jeu de procédures de construction de structures de données et d'accès aux informations qui y sont stockées est rudimentaire et incomplet, mais nous pourrons le perfectionner et le raffiner au fur et à mesure de nos progrès en Scheme.

 


6.2 Représentation et manipulation des listes

 

6.2.1 Description et représentation externe

Une des structures de données les plus simples et commodes que nous puissions construire avec des assemblages de doublets est l'enchaînement que nous pouvons représenter ainsi :

 

 

Figure 6.2: Structure de liste
\includegraphics[scale=0.8]{../Images/Const-listes/liste.epsi}67

 

Cette structure est celle que Scheme utilise pour représenter les listes. Le car de chaque doublet est l'expression à placer dans la liste. Son cdr est le doublet suivant dans la chaîne. Le cdr du dernier doublet signale la fin de la liste par une valeur spéciale représentée dans notre graphique par une boîte traversée d'une diagonale et nommée liste vide ou marqueur de fin de liste.

Comment se note en Scheme le marqueur de fin de liste ? Ceci nous impose une petite digression. Nous avons déjà vu et utilisé des listes, ce sont celles qui nous servent à noter les appels de procédures et les formes spéciales. Le premier élément d'une telle liste doit être le nom d'une forme spéciale ou d'une procédure :

 

: (+ 3 4)
7

: (a z)
*** ERROR - Operator is not a PROCEDURE
(a z)

La liste (a z) est bien une liste valide, mais comme les listes ne sont pas des objets auto-évaluants on ne peut pas l'écrire ainsi. Il faut utiliser la forme spéciale quote :

 

: '(a z)
(a z)

De même la liste vide pourrait se noter (), mais ce n'est pas une syntaxe valide en Scheme. C'est la forme spéciale quote qui va nous permettre de résoudre ce problème :

 

: '()
()

Cette question de notation nous a permis de voir (à nouveau) qu'il convenait de distinguer la forme interne de l'objet (celle qu'imprime l'évaluateur) de la forme externe (celle que nous écrivons à l'invite du lecteur).

Cet obstacle surmonté, nous pouvons introduire la façon de définir en Scheme la structure représentée par la figure 6.2 :

 

1:=> (cons "Haddock"
        (cons "Tintin"
              (cons "la Castafiore"
                    (cons "Tournesol" '()))))
(Haddock Tintin la Castafiore Tournesol)

Cette cascade d'appels à cons construit la chaîne de doublets qui constitue la liste. Nous étudierons de plus près le lien entre les listes et les doublets. Mais tout d'abord voici une autre liste :

 

1:=> (define a 1)

1:=> (define b 2)

1:=> (define c 3)

1:=> (define d 4)

1:=> (define une-liste  ;; 92 $[\mathcal{C}]$97
       (cons a (cons b (cons c (cons d '())))))

Cette notation a l'avantage de mettre en lumière la structure en doublets de la liste, mais l'inconvénient d'une certaine lourdeur. Scheme possède une fonction list, qui permet la notation ci-dessous, exactement équivalente à la précédente mais plus légère à écrire :

 

1:=> (define une-liste (list a b c d))  ;; 92 $[\mathcal{D}]$97

1:=> une-liste
(1 2 3 4)

La fonction list accepte un nombre quelconque d'arguments et construit une nouvelle liste constituée des valeurs des arguments :

 

1:=> (list a b c d)  ;; 92 $[\mathcal{E}]$97
(1 2 3 4)

1:=> '(a b c d)      ;; 92 $[\mathcal{F}]$97
(A B C D)

On notera la différence entre les lignes $[\mathcal{E}]$ et $[\mathcal{F}]$ : les deux écritures construisent une liste, mais la première avec les valeurs liées aux variables désignées par les symboles a, b, c et d, et la seconde avec les symboles non évalués, conformément aux principes de la forme spéciale quote.

 

1:=> (list 1 2 3 4)        ;; 92 $[\mathcal{G}]$97
(1 2 3 4)

1:=> '(1 2 3 4)        ;; 92 $[\mathcal{H}]$97
(1 2 3 4)

Pour $[\mathcal{G}]$ et $[\mathcal{H}]$, les deux écritures semblent donner le même résultat, mais c'est uniquement parce que les nombres sont des objets auto-évaluants, dont par définition l'expression ne se distingue pas de la valeur.

Incidemment, voici (enfin !) la représentation d'un doublet qui ne serait pas une liste :

 

1:=> (cons 1 2)
(1 . 2)

Notez bien que le point est précédé et suivi d'espaces blancs. L'oubli de ces espaces est une erreur banale mais fatale.

 

6.2.2 Les listes sont des doublets

La fonction list n'est qu'une facilité d'écriture, la vraie façon de construire une liste, c'est avec cons. Reprenons l'exemple $[\mathcal{D}]$ :

 

(define une-liste
  (cons a (cons b (cons c (cons d '())))))

Le premier cons définit un doublet tel que :

 

1:=> (car une-liste)
1 ;; valeur de a
1:=> (cdr une-liste)
(2 3 4) ;; (list b c d)

ce qui peut se représenter ainsi :

 

 

Figure 6.3: Les listes sont des doublets
\includegraphics{../Images/Const-listes/liste-doublet.epsi}59

 

L'équation fondamentale de cons, car et cdr nous permet d'écrire :

 

1:=> (cons a (list b c d))
(1 2 3 4)

Ceci élargit quelque peu notre vision des doublets et met en lumière le caractère récursif de la structure de liste, dont la définition peut être formulée ainsi :

 

Exemple :

 

1:=> (cons a '())
(1)

Dans le contexte d'une structure de liste non vide, les sélecteurs car et cdr permettent d'accéder aux éléments de la liste L :

 

Le dernier doublet d'une liste est toujours de la forme : (cons a '()), où l'important est '(). Une structure de doublets qui ne se termine pas de la sorte n'est pas une liste (ce qui n'interdit pas de la définir et de l'utiliser). Une liste bien formée est aussi nommée « liste propre ».

 

6.2.3 Manipulation de listes

Programmer en Scheme exige une maîtrise parfaite des listes, qui sont la structure de base du langage. L'expérience montre que la représentation « boîtes et pointeurs » et le retour à la structure de doublets sous-jacente sont les bons moyens pour analyser sans se tromper une liste un peu compliquée.

Les principes de base de la structure de liste sont les suivants :

 

Voici quelques exemples.

 

6.2.3.1 Premier exemple

Soit une liste dont l'interprète affiche la valeur sous cette forme (que nous avons appelée forme interne) :

 

(a b (a . b))

 

 

Figure 6.4: Premier exemple
\includegraphics[scale=0.8]{../Images/Const-listes/listes-ex1.epsi}67

 

L'expression qui construit cette structure est, par exemple :

 

1:=> (list 'a 'b (cons 'a 'b))
(a b (a . b))

ou :

 

1:=> (cons 'a (cons 'b (cons (cons 'a 'b) '())))
(a b (a . b))

Cette dernière expression est en fait la plus fondamentale, qui nous donne l'assurance que notre structure est bien correcte.

 

1:=> (list? (cons 'a (cons 'b (cons (cons 'a 'b) '()))))
#t

La relation entre la forme interne de la S-expression, affichée par Scheme, et l'expression qui la construit (ou les expressions capables de la construire) peut être complexe, mais voici un programme6.1qui, à partir d'une S-expression, élabore une expression pour la construire :

 

(define (reconstruire exp)
   (if (pair? exp)
       (list 'cons (reconstruire (car exp))
                   (reconstruire (cdr exp)))
       (list 'quote exp)))

ou si on préfère la forme abrégée :

Construire l'expression qui construit la forme

(define (reconstruire exp)
  (cond ((pair? exp)
         (list 'cons (reconstruire (car exp))
               (reconstruire (cdr exp))))
        ((eqv? exp '()) "'()")
        ((symbol? exp)
         (string-append "'" (symbol->string exp)))
        (else exp)))

74

ce qui introduit la conditionnelle cond41 6.2.

 

6.2.3.2 Second exemple

 

(((a) b . c) () . d)

 

 

Figure 6.5: Second exemple
\includegraphics[scale=0.8]{../Images/Const-listes/listes-ex2.epsi}67

 

 

1:=> (cons (cons (cons 'a '()) (cons 'b 'c)) (cons '() 'd))
(((a) b . c) () . d)

On vérifie qu'il y a bien autant de boîtes doubles que de cons et que :

 

1:=> (list? (cons (cons (cons 'a '()) (cons 'b 'c)) (cons '() 'd)))
#f

La structure définie ici n'est pas une liste propre.

 

6.2.3.3 Troisième exemple

Les structures construites par make-capitaine en $[\mathcal{B}]$ sont-elles des listes propres ?

 

1:=>(list?
      (make-capitaine "Haddock" "50 ans" "Astrolabe" "40 t"))
#f

La forme de la représentation « boîtes et pointeurs »de la figure 6.1 nous aurait permis de le prévoir.

 

1:=> (make-capitaine "Haddock" "50 ans" "Astrolabe" "40 t"))
((Haddock Astrolabe . 40 t) . 50 ans)

Des formes telles que celle-ci sont parfois appelées listes pointées.

 


6.2.4 Représentation interne des listes

Un langage de programmation de haut niveau (destiné à écrire des programmes pas nécessairement destinés à piloter directement les rouages matériels de l'ordinateur) doit procurer un niveau d'abstraction suffisant pour éviter au programmeur d'avoir à connaître les détails d'implantation des objets qu'il manipule au moyen des constructions du langage. Parfois, acquérir une connaissance d'aspects un peu internes, un peu concrets est néanmoins nécessaire à une bonne compréhension de certains objets ou mécanismes. Il convient de choisir le bon niveau où se placer, entre le trop abstrait qui ne permet pas l'acte de programmer et le trop concret, non pertinent (ici, l'électronique par exemple).

Dans le cas des doublets et des listes, il se trouve qu'il faut connaître le principe de leur représentation pour comprendre certains programmes, et que cette représentation est explicable en termes suffisamment proches de notre propos actuel.

En fait, la représentation interne des doublets et des listes correspond bien à la représentation « boîtes et pointeurs » de la section 6.1.1.2 page [*]. Il suffit de savoir que la liaison établie dans l'environnement courant entre une variable et sa valeur se traduit par le stockage de la valeur dans la mémoire du système. Pour réaliser ce stockage, au moment de la création de l'objet a lieu une allocation d'espace mémoire. Le système de programmation se charge de cette opération et le programmeur (du moins en Scheme) n'a pas à la programmer.

En général les objets scalaires occupent une « case » de la mémoire (sans préciser plus la nature de cette case), les objets structurés une collection de cases. Les cases pour les objets scalaires sont généralement allouées dans une région de la mémoire appelée la pile (stack), les collections de cases pour les objets structurés dans une région appelée le tas (heap) (ces notions seront exposées au chapitre 8).

Les doublets sont construits par cons, traditionnellement sur le tas. Notre représentation graphique figure un doublet par une « boîte double » : il suffit de se dire que cette boîte double correspond à deux cases mémoire sur la pile, une contenant un pointeur vers le car et l'autre un pointeur vers le cdr. Si le car (resp. le cdr) du doublet est lui-même un doublet, la case qui le représente contiendra un pointeur vers ce doublet. L'adresse d'un doublet est l'adresse de la « boîte double » qui contient les pointeurs vers son car et son cdr.



Maintenant que nous connaissons la réalité physique sous-jacente à nos boîtes et pointeurs, le sens de certaines expressions va s'éclairer6.3 :

 

(define L1 '(b c d))
(define L2 (cons 'a L1))
(define L3 (cons 'a (cddr L2)))

Ces trois listes se représentent par les diagrammes de la figure 6.6. On voit qu'elles partagent physiquement des boîtes, donc des éléments.

 

 

Figure: Listes à éléments partagés
\includegraphics[scale=0.8]{../Images/Const-listes/listes-partage.epsi}67

 

 

6.3 Exemples d'opérations sur les listes

 

6.3.1 append

Une des opérations que l'on souhaite réaliser le plus souvent est de prendre deux (ou plusieurs) listes pour constituer une nouvelle liste, constituée des éléments de la première liste argument suivis de ceux des listes arguments suivantes. Essayons avec deux listes :

 

: (define (concatener-2 L1 L2)
    (if (null? L1)
      L2
      (cons (car L1)
            (concatener-2 (cdr L1) L2))))

: (concatener-2 '(1 2 3 4) '(5 6 7))
(1 2 3 4 5 6 7)

: (concatener-2 '() '(5 6 7))
(5 6 7)

: (concatener-2 '(1 2 3 4) '())
(1 2 3 4)

En fait, Scheme nous fournit une procédure toute faite qui réalise cette fonction pour un nombre quelconque de listes et qui s'appelle append.

On profitera de cet exemple pour y observer la structure élémentaire du traitement récursif des listes.

 

6.3.2 reverse

Une autre opération courante consiste à prendre une liste en argument et à créer une liste nouvelle constituée des éléments, en ordre inverse, de la liste argument :

 

: (define (retourner L)
    (if (null?  L)
      '()
      (concatener-2 (retourner (cdr L))
                    (list (car L)))))

: (retourner '(1 2 3 4))
(4 3 2 1)

Il existe une procédure prédéfinie nommée reverse.

 

6.3.3 map

On peut vouloir, à partir d'une liste donnée, construire une nouvelle liste dont chaque élément soit le résultat de l'application d'une même procédure proc à chaque élément de la liste de départ :

 

: (define (app-liste proc L)
    (if (null? L)
        '()
        (cons (proc (car L))
              (app-liste proc (cdr L)))))

: (app-liste car '((1 2) (2 3) (3 4)))
(1 2 3)

La procédure prédéfinie s'appelle map et accepte plusieurs listes de même longueur en arguments, ce qui permet de l'utiliser avec des procédures à plusieurs arguments ; proc doit accepter autant d'arguments qu'il y a de listes et s'applique en prenant chaque fois un argument dans chaque liste, jusqu'à épuisement.

 

6.3.4 apply

La syntaxe de l'application d'une procédure proc à ses arguments arg1, ... argn est la suivante :

 

(proc arg1 ... argn)

mais comment faire si ces arguments sont déjà rangés dans une liste ?

 

L = (arg1 ... argn)

La procédure apply résout ce problème syntaxique :

 

(apply proc <Liste d'arguments>)

ainsi :

 

: (apply + '(4 5 2 9))
20

Comme map renvoie une liste d'évaluations, sa combinaison avec apply peut être commode :

 

: (define Liste-des-ages            92 $[\mathcal{J}]$97
    (list
      (cons "Haddock" 50)
      (cons "Tintin" 20)
      (cons "Milou" 5)))

: (define (somme-des-ages L)
    (apply + (map cdr L)))

: (somme-des-ages Liste-des-ages)
75

 

6.4 Prédicats d'équivalence

Les trois prédicats d'équivalence de Scheme, equal?, eqv? et eq?, partagent avec les relations d'équivalence de la mathématique les propriétés de symétrie, de réflexivité et de transitivité. eq? est le plus fin et le plus discriminant des trois, equal? le plus conciliant ou le plus grossier selon l'angle d'appréciation.

 

6.4.1 eqv?

 

(eqv? obj1 obj2)

La procédure eqv? retourne #t si obj1 et obj2 peuvent être considérés comme le même objet. Cette définition prête à interprétation, la norme [CKR98] donne quelques exemples plus ou moins éclairants.

La procédure eqv? retourne #t si :

 

1.
obj1 et obj2 sont tous les deux soit #t soit #f ;
2.
obj1 et obj2 sont tous les deux des symboles et :

(string=? (symbol->string obj1) (symbol->string obj2)) \(\to\) #t

3.
obj1 et obj2 sont tous les deux des caractères et sont le même caractère au sens de la procédure char=? ;
4.
obj1 et obj2 sont tous les deux la liste vide ;
5.
obj1 et obj2 sont tous les deux des doublets, des chaînes de caractères ou des vecteurs qui dénotent les mêmes positions en mémoire (voir 6.2.4).

La procédure eqv? retourne #f si :

6.
obj1 et obj2 sont de types différents ;
7.
l'un ou l'autre de obj1 et obj2 est #t et l'autre est #f ;
8.
obj1 et obj2 sont tous les deux des symboles et :

(string=? (symbol->string obj1) (symbol->string obj2)) \(\to\) #f

9.
obj1 et obj2 sont des nombres pour lesquels la procédure = retourne #f ;
10.
obj1 et obj2 sont des caractères pour lesquels la procédure char=? retourne #f ;
11.
l'un ou l'autre de obj1 et obj2 est la liste vide et l'autre ne l'est pas ;
12.
obj1 et obj2 sont des doublets, des chaînes de caractères ou des vecteurs qui dénotent des positions de mémoire distinctes.

Exemples :

 

    (eqv? 'a 'a) \(\to\) #t
    (eqv? 'a 'b) \(\to\) #f
    (eqv? 2 2) \(\to\) #t
    (eqv? '() '()) \(\to\) #t
    (eqv? 100000000 100000000) \(\to\) #t
    (eqv? (cons 1 2) (cons 1 2)) \(\to\) #f (en vertu de 12)

 

6.4.2 eq?

eq? est similaire à eqv? mais peut dans certains cas détecter des différences plus subtiles que eqv?. Ces deux prédicats sont garantis avoir le même comportement lorsqu'appliqués à des symboles, à des booléens, à la liste vide, aux doublets et à des chaînes et des vecteurs non vides. Ils peuvent avoir des comportements différents lorsqu'appliqués à des nombres ou à des caractères, mais ils retourneront toujours #t ou #f, et eq? ne renverra vrai que dans les cas où eqv? renverrait aussi vrai. Le mécanisme sous-jacent à eq? est généralement la comparaison des emplacements en mémoire.

Dans le système Bigloo eq? et eqv? sont équivalents (sic). Compte tenu de la grande limpidité du texte [CKR98] à ce sujet, ce parti pris ne semble pas déraisonnable.

 

6.4.3 equal?

equal? compare récursivement les contenus des doublets, des vecteurs et des chaînes et applique eqv? aux autres objets, notamment aux atomes. Deux objets sont généralement égaux au sens de equal? si l'interprète les imprime de la même façon.

 

6.4.4 Comparaison de listes

Munis de ces prédicats et des notions sur la représentation physique des listes introduites en 6.2.4 page [*] nous allons pouvoir comparer des listes. Reprenons l'exemple de 6.2.4 :

 

(define L1 '(b c d))
(define L2 (cons 'a L1))
(define L3 (cons 'a (cddr L2)))

 

 

Figure: Listes à éléments partagés
\includegraphics[scale=0.8]{../Images/Const-listes/listes-partage.epsi}67

 

Le partage physique des emplacements en mémoire de certains doublets se traduit par la satisfaction du prédicat d'équivalence convenable :

 

(eq? (cdr L1) (cdr L3)) \(\to\) #t

De même, considérons la procédure suivante :

 

(define (copie L)
    (if (null? L) L
        (cons (car L) (copie (cdr L)))))

(define L4 (list (list 1 2) 3 4))

Nous en déduisons :

 

(eq? (car L4) (car (copie L4))) \(\to\) #t

La satisfaction du prédicat eq? dénote le partage physique de mémoire, alors que :

 

(eq? L4 (copie L4)) \(\to\) #f
(eq? (cdr L4) (cdr (copie L4))) \(\to\) #f

 


6.5 Listes d'associations (a-listes)

Reprenons l'exemple ci-dessus ($[\mathcal{J}]$) :

 

: Liste-des-ages

(("Haddock" . 50) ("Tintin" . 20) ("Milou" . 5))

Une telle liste de doublets s'appelle une liste d'associations, ou a-liste. Chaque doublet associe une valeur (le cdr du doublet) à une clé (le car du doublet).

C'est une structure de données très commode et d'un usage très fréquent, pour réaliser des tables de correspondance par exemple. Il existe des procédures prédéfinies pour y retrouver des valeurs en fonction des clés. Le principe de la recherche dans une a-liste consiste à déterminer le doublet dont la clé est égale à celle la valeur cherchée, par exemple avec la procédure assoc :

 

: (assoc "Haddock" Liste-des-ages)
("Haddock" . 50)

assoc effectue les comparaisons nécessaires à la recherche avec la sémantique de equal?, ce qui convient bien pour les chaînes de caractères. Les procédures cousines assq et assv mettent respectivement en \oeuvre eq? et eqv? .

 


6.6 Citation encore : quasiquote, virgule et arobas

41 41 44

La forme spéciale quote a une cousine, quasiquote, qui se comporte presque de la même façon, et qui s'abrège en `. Utilisée seule, on ne voit pas de différence :

 

: `(x y)
(x y)

Les éléments de la liste ne sont pas évalués, il en aurait été de même avec quote.

Mais, dans une liste « quasi-quottée », il nous est possible de demander l'évaluation de certains éléments en les précédant d'une virgule :

 

: (define a 1)
a

: `(a ,a)
(a 1)

Au lieu de quotter6.4les éléments qui ne doivent pas être évalués, on « quasi-quotte » toute la liste et on marque d'une virgule les éléments à évaluer.

Nous avons une troisième possibilité de choix de l'action à infliger aux éléments d'une liste « quasi-quottée » : si un élément est précédé du couple de caractères « ,@ » (virgule-arobas), il sera évalué, mais sa valeur devra être une liste, et ce sont les éléments de la liste qui viendront prendre la place du symbole :

 

: (define L '(a b c))
L

: (define a 1)
a

: `(m n o ,a ,@L)
(m n o 1 a b c)

On remarquera que l'effet du couple « ,@ » aurait pu être obtenu, de façon moins concise mais plus facile à lire, avec append.

Nous verrons que ces formes sont très utiles lorsque nous voudrons écrire des procédures qui écrivent des procédures.

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