Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : C/C++ - la liste, aspects fonctionnels avec C/C++ et Cami
(Article écrit par Gilles Dridi et extrait d'Amiga News - janvier 1997)
|
|
Un itérateur avec C/C++ ou un type prédéfini d'un langage de programmation ?
La dernière fois, nous avons vu un mécanisme
de C++ : la fonction virtuelle. Cette fois-ci, nous allons voir le type de données très utilisé : la liste. Ceci nous permettra
de mieux appréhender la conception d'Exec et les notions de programmation orientée par les objets.
Pour ceux qui s'intéressent au module-bibliothèque dont j'ai dit que nous parlerions, vous pouvez vous référer à cet
article.
L'abstraction, ou comment définir notre type liste
La liste est un type de données simple comme le tableau, et à cause de cela, on a souvent besoin de les utiliser. Évident de
l'implanter, me direz-vous ? A priori, oui. Mais qu'est-ce que c'est, exactement, une liste ?
Un tableau a une dimension ou vecteur, c'est une suite d'éléments comme les touches 1;2;3 du pavé numérique, un tableau à deux
dimensions ou matrice : le pavé numérique de 1 à 9 ou les pixel de l'écran. Si je tape sur le clavier 1 puis 2 puis 3, j'ai une
liste. Pourquoi ?
Parce que j'ai séparé dans le temps, ma frappe, et que je ne regarde plus la suite de chiffre 1;2;3 du pavé numérique. Je tape :
c'est une action. D'une autre façon, je peux considérer une suite d'actions : taper sur 1 puis sur 2 puis sur 3. C'est alors, à
l'instar du tableau à une dimension, un vecteur d'actions.
Toutefois, si je veux continuer à taper, par exemple sur la touche 4, il me faut à nouveau revenir aux listes ; faire la différence
entre ce que je vois et ce que je fais : la finalité fonctionnelle du type.
Le type correct
La différence formelle entre notre vecteur et notre liste de chiffres 1;2;3, c'est que l'un est une structure de données statique,
l'autre dynamique : je vois 1;2;3 mais je tape 1 puis 2 puis 3 sur le clavier. Pour donner une image : la liaison entre chaque
chiffre, quand je les tape, ce sont les articulations entre chaque doigt, sauf pour ceux qui tapent avec un doigt bien sûr !
On pourrait dire : si on voit l'ensemble des éléments, je le mets sous la forme du tableau, sinon, j'en fais une liste (ou autre
structure dynamique).
Remarque : il existe encore un autre type de données, dont la gestion est spéciale, qui est à part, et qui s'appelle table de
hachage. Celle-ci se concentre sur les caractéristiques de l'élément appartenant à un ensemble, et permet de retrouver un élément
à partir de celles-ci. Par exemple, notre système de fichiers l'utilise.
L'objet liste avec C++
On reprend le programme d'exemple de la dernière fois : le type Fruit. Chaque instance est chaînée à la suivante et on parcourt
cette liste, pour afficher (à l'écran) les identifiants de chaque fruit. Lorsqu'on parcourt, on fait presque en C/C++ :
variable pointeur initialisé sur un élément de liste de fruit.
tantQue(pointeur valide) {
affiche_identifiant(accès par le pointeur à l'identifiant du fruit);
mise à jour du pointeur sur l'élément suivant;
}
|
On aimerait bien s'abstraire de la représentation interne ou l'implantation de la liste avec cette manipulation de variables pointeurs,
pour avoir plutôt un algorithme spécifié par : "parcourir la liste et faire pour chaque élément : afficher son
identifiant".
Alors on va introduire ce qu'on appelle un itérateur : chaque arrêt sur un élément déclenche une action : afficher l'identifiant fruit.
Nous allons discuter succinctement de l'inconvénient de l'itérateur. Une partie de l'algorithme est incorporée (embedded) dans
l'objet itérateur : la gestion du pointeur : initialisation, validité, mise à jour du pointeur.
Aparté : si nous disons que les algorithmes sont "noyés" dans un objet ou un ensemble d'objets, nous sommes péjoratifs. Prenons
l'exemple d'un gâteau au chocolat à partir de sachets de préparations, ou avoir une recette de cuisine bien détaillée en
utilisant les ingrédients de base, revient quand même à l'obtention d'un gâteau au chocolat.
Il faudra, pour le fabricant des sachets de préparation, connaître les ingrédients de base et au "cuisinier-utilisateur" savoir lire
la recette et éventuellement connaître la composition des sachets de préparation ; ne serait-ce que pour justifier si son gâteau
est bon ou mauvais !
Ainsi, on peut se demander si en fournissant une telle abstraction (l'itérateur), on est encore sûr d'avoir une liste comme
représentation interne des éléments. On fera confiance au nom donné : itérateur de liste, et aux noms donnés aux fonctions de
celui-ci : ici, itérateur de liste de fruit et estFini(), courant(), prochain().
Conclusion sur l'itérateur
C'est un bon compromis car on n'a plus de mise à jour à faire du pointeur "ptrF". Notre algorithme d'itérateur fonctionnerait aussi
pour un vecteur de Fruit. De plus, on peut réutiliser notre itérateur de nouvelles fois sans crainte de faire une erreur
(plantant le programme et le système sur Amiga), dans la mise à jour du pointeur "prtF". Mais, on remarquera que l'erreur susceptible
d'exister, lors de la mise au point, sera dans l'itérateur. C'est un bon point pour la maintenance. L'itérateur a été mis
au point, par nos soins, avec les ingrédients de base : pointeur et algorithme de parcours de liste. L'itérateur associé au type
de notre liste de fruits est ce qu'on appelle une structure de données active. Il est basé sur une machine à état avec une seule
variable booléenne d'états : "fin".
Autre exemple avec Cami
La liste avec un langage fonctionnel qui a un type liste (list) prédéfini. Voici le même exemple avec un langage dit fonctionnel.
J'ai choisi le système itératif "Cami", parce qu'il nous permettra d'affiner à la fois le concept de type abstrait/concret grâce
à son système de typage, et de structures de données actives (l'itérateur) par ses types de données prédéfinis et son aspect
fonctionnel. Passons sous interpréteur :
Conclusion sur le système interactif
Cami
On a utilisé le type de liste prédéfini, pour l'affichage, on a simplement laissé le système nous afficher la liste de fruits ;
celui-là est interactif. On s'aperçoit aussi, et c'est important, que l'on peut définir des types polymorphes. De plus, le système
Cami comporte un sous-système très élaboré de typage qui nous a permis de comprendre rapidement ce qu'était son propre type de liste
polymorphe. S'il fallait utiliser une liste polymorphe avec C/C++, on pourrait le faire en paramétrant les éléments de liste
(template) mais le système Cami interactif est beaucoup plus puissant de ce point de vue là. Toutefois, on a vu qu'avec C/C++, on peut
aussi définir de nouveaux types mais la différence est qu'on est obligé d'attendre la compilation pour détecter les incompatibilités
de types, les accès à des données privées... (à moins d'avoir un interpréteur). Alors qu'avec Cami, le vérificateur de type nous
donne tout de suite le type de l'objet (signature pour une fonction) ou génère une incompatibilité de type, ou encore nous
permet de lever une exception lors de l'exécution.
Synthèse
Bien sûr, il nous faudra étudier d'autres langages fonctionnels tels que les Lisp ou d'autres langages (compilés ou optimisés)
à objets tels que le Pascal Objet, Eiffel, Ada, Smalltalk pour avoir un plus grand aperçu des possibilités de chacun : paquetage
prédéfini, compilation/interprétation, le tout objet, etc. Cette première approche avec C/C++ et Cami en étudiant le type de donnée
(la liste) nous a permis de mettre à jour l'abstraction (liste), de faire des parallèles entre un système interactif et compilé,
entre impératif et le fonctionnel. On a vu que l'applicateur est intrinsèque dans un LF et l'itérateur orienté impératif.
De plus, avec la liste, on s'aperçoit qu'elle devrait constituer le fondement de tout cadre de travail (bibliothèque) d'un
langage "plus qu'évolué".
Retenons que le système Cami est interactif, contient des types de base "prédigérés" ainsi qu'un vérificateur de type, etc.
Il conviendra mieux au débutant voulant s'essayer à l'approche fonctionnelle et le modèle de type abstrait dans l'approche
objet (on peut aussi faire, sans risque grâce au vérificateur de type et normalement aux exceptions bien définies, de l'impératif
avec Cami). Les plus expérimentés ou fervents de C/C++ pourront l'utiliser avec plaisir, mais surtout vérifier rapidement la
cohérence des signatures des méthodes d'un objet et les tester rapidement sur un jeu de données.
Soutenez le travail de l'auteur
|
|
|
