ISBN 0-32149362-1 Chapitre 6 Types de données. Copyright © 2007 Addison-Wesley. All rights reserved.1-2 Chapitre 6: Sujets Introduction Types de données

ISBN 0-321—49362-1

Chapitre 6

Types de données

Copyright © 2007 Addison-Wesley. All rights reserved. 1-2

Chapitre 6: Sujets

• Introduction• Types de données élémentaires• Les chaînes de caractères• Types ordinaux définis par l'usager• Les tableaux• Les tableaux associatifs• Les enregistrements• Les unions• Pointeurs et références


Introduction

• Type de données: ensemble de valeurs + opérations

• Un descripteur de variable est l'ensemble de ses attributs.

• Un objet représente une instance d'un type de donnée abstrait (défini par l'usager dans le livre).


Types de données élémentaires

• Fournis par presque tous les langages de programmation

• Ne sont pas définis en termes d'autres types de données.

• Réflètent quelques fois le matériel (ex. les entiers)


Types de données élémentaires:Les entiers

• Réflète presque toujours le matériel. Donc l'implémentation est triviale.

• Il peut y avoir plusieurs types d'entiers différents dans un langage.

• Entier signé en Java: byte (8 bits), short (16 bits), int (32 bits)et long (64 bits).

• C++ et C# fournissent en plus des entiers non signés.


Types de données élémentaires: Les nombres en points flottants

• Modélisent une approximation des nombres réels.

• Langages scientifiques: au moins deux types (e.g., float et double) quelques fois plus.

• Réflètent habituellement le matériel mais pas toujours.

• IEEE Floating-PointStandard 754


Types de données élémentaires Les nombres décimaux

• Pour les applications liées au monde des affaires– Essentiel en COBOL– C# offre un type decimal

• Nombre fixe de chiffre décimaux• Avantage: précision (0.1 ne peut pas être

représenté de façon exact en binaire)• Désavantages: étendue des valeurs

limitée, mauvaise utilisation de la mémoire


Types de données élémentaires Les nombres complexes

• Supportés par Fortran et Python• En Python la partie imaginaire est un

nombre suivit de la lettre j– 7 + 3j

• Ces langages supportent aussi les opérateurs arithmétiques sur les complexes.


Types de données élémentaires Les booléeens

• Le plus simple des types– Absent de C89 mais inclu dans C++ et C99

• Deux éléments: "vrai" et "faux"• Souvent implémenté par un octet

– car sur la plupart des ordinateurs on ne peut pas accéder à un seul bit de façon efficace.

• Avantage: lisibilité


Types de données élémentaires Les caractères

• Encodés sous forme numérique• Largement répendu: ASCII

– 8 bits– pas d'accent

• Alternative: Unicode– 16 bits– Inclu les caractères de la plupart des langues

naturelles– Java est un des premiers langages à supporter

Unicode.– C# et JavaScript supporte aussi Unicode


Les chaînes de caractères

• La valeur d'une variable de type chaîne de caractères est une séquence de caractères.

• Considérations de conception:– Est-ce un type élémentaire ou un tableau?– La longueur doit-elle est statique ou

dynamique?


Opérations sur les chaînes

• Opérations typiques:– affectation et copie– Comparaison (=, >, etc.) – Concaténation– Référence à une sous-chaîne– Recherche de motif (pattern matching)


Les chaînes dans certains langages• C and C++: tableau se terminant par NUL

– librairie string.h– peu sécure– C++ contient la classe string

• SNOBOL4: langage spécialisé pour la manipulation de chaînes.

• Java: type élémentaire via les classes String et StringBuffer

• Python: type élémentaire (immuable) mais se comporte comme des tableaux.

• JavaScript, Ruby, PHP et Perl: type élémentaire + opérations permettant la recherche de motifs via expressions régulières.


Évaluation du type chaîne

• Facilite l'écriture• Faible coût lorsqu'il s'agit d'un type

élémentaire de longueur statique –Pourquoi s'en passer?

• Le coût pour implémenter la longueur dynamique plus difficile à justifier.


Implémentation des chaînes

• Longueur statique: Descripteur requis seulement durant la compilation.

• Longueur dynamique limitée: Peut nécessiter un descripteur pendant l'exécution (pas en C et C++)


Implémentation des chaînes (suite)• Longueur dynamique: nécessite une

gestion de la mémoire plus complexe.• 3 approches:

– liste chaînée: beaucoup d'espace mémoire– tableau de pointeurs vers des caractères

dans le tas: beaucoup d'espace mémoire mais le traitement des chaînes est plus rapide.

– tableau de caractères: Difficile à gérer lorsque la longueur varie beaucoup.


Types définis par l'usager: Les types ordinaux

• Type dont les valeurs peuvent être associées aux entiers.

• Exemples de type ordinaux élémentaires en Java:– integer– char– boolean


Les énumerations

• Toutes les valeurs sont des noms constants fournies lors de la définition.

• Exemple en Cenum days {mon, tue, wed, thu, fri, sat, sun};

• Considération conceptuelle– Est-ce qu'un nom constant peut apparaître dans plus

d'une énumerations? Si oui, est que le type de ce nom constant est vérifié?

– Y a-t-il conversion par défaut des types énumération vers les entiers?

– Y a-t-il conversion par défaut d'un autre type vers une énumération?


Évaluation des énumérations

• Facilite la lisibilité (e.g. pas besoin de coder une couleur en un nombre)

• Augmente la fiabilité (e.g. le type peut être vérifié à la compilation:– opérations (ne pas additionner 2 couleurs) – Vérification des limites– Ada, C#, et Java 5.0 contrairement à C++ ne

forcent pas la conversion de types des énumérations vers les entiers.


Types intervalles

• Intervalle de valeurs d'un type ordinal– Exemple: 1..100 est un intervalle des entiers

• Les intervalles en Adatype Days is (mon, tue, wed, thu, fri, sat, sun);

subtype Weekdays is Days range mon..fri;

subtype Index is Integer range 1..100;

Day1: Days;

Day2: Weekday;

Day2 := Day1; (valide sauf si Day1 vaut sat ou sun)


Évaluation des intervalles

• Lisibilité– Rend clair le fait que la variable ne peut

contenir qu'une intervalle de valeurs

• Fiabilité– L'affectation d'une valeur située en dehors des

limites d'une variable de type intervalle est détectée comme une erreur.


Implémentation des types ordinaux définis par l'usagers

• Les énumérations sont implémentées comme les entiers.

• Les intervalles sont implémentées comme leur type parent. Du code supplémentaire est inséré par le compilateur pour restreindre les affectations qui ne respectent pas les limites.


Les tableaux

• Un tableau est une suite ordonnée d'éléments de même type. Chaque élément est identifié par sa position relative au premier élément.


Les tableaux:Considération de conception

• Quels sont les types valides pour les indices?• Les limites sont-elles vérifiées?• À quel moment l'intervalle d'indices est-elle

fixée?• Quand l'allocation de la mémoire a-t-elle lieu?• Quel est le nombre maximal d'indices

(dimentions)?• Les tableaux peuvent-ils être initialisés?• Peut-on référer à une partie de tableau?


Les indices de tableaux

• Fonction des indices vers les éléments nom_du_tableau (liste_des_indices) élément

• Syntaxe:– FORTRAN, PL/I, Ada utilisent des parenthèses

• Les concepteurs de Ada ont utilisé des parenthèses spécifiquement pour montrer la similitude entre les références aux tableaux et les appels de fonctions.

– La plupart des autres langages utilisent des crochets.


Types d'indices

• FORTRAN, C et Java: Entiers seulement• Pascal et Ada: n'importe quel type ordinal

• C, C++, Perl, et Fortran ne vérifient pas les limites

• Java, ML, C# et Ada font une vérification des limites (cette vérification peut être supprimée en Ada).


Catégories de tableaux

• Statique: l'intervalle des indices et l'espace mémoire sont attribués statiquement– Avantage: efficacité (temps)

• Semi-dynamique sur pile: L'intervalle des indices est attribuée statiquement mais la mémoire est attribuée dynamiquement lors de la déclaration– Avantage: efficacité (espace)


Catégories de tableaux (suite)

• Dynamique sur pile: L'intervalle des indices et l'espace mémoire sont attribués en cours d'exécution et demeurent inchangés par la suite.– Avantage: flexibilité (la taille du tableau n'a pas

besoin d'être connu à l'avance)

• Semi-dynamique sur tas: L'intervalle des indices et l'espace mémoire sont attribués à l'exécution mais demeurent inchangé par la suite. L'espace mémoire est prise sur le tas.



• Dynamique sur tas: L'intervalle des indices et l'espace mémoire peut changer en cours d'exécution. – Avantage: flexibilité (les tableaux peuvent

grossir et rétrécir pendant l'exécution)



• C et C++ utilisent le mot-clé static pour définir des tableaux statiques.

• C et C++ utilisent par défaut des tableaux semi-dynamiques sur pile.

• En Ada les tableaux peuvent être dynamique sur pile.

• Fortran, C# et Java: semi-dynamique sur pile

• C# possède une autre classe de tableaux ArrayList qui sont dans la catégorie dynamique sur tas.

• Perl, Python, Ruby et JavaScript supportent les tableaux dynamiques sur tas (ces tableaux peuvent êtres hétérogènes)


Initialisation des tableaux

• Certains langages permettent l'initialisation au moment de l'allocation de l'espace mémoire.– Exemple en C, C++, Java ou C#

int list [] = {4, 5, 7, 83} – Les chaînes de caractères en C

char name [] = “freddie”;– Tableaux de chaînes en C

char *names [] = {“Bob”, “Jake”, “Joe”];– Tableau de chaînes en Java

String[] names = {“Bob”, “Jake”, “Joe”};


Initialisation des tableaux (suite)

• Exemple en Ada:

tab1: array (1..5) of Integer := (1,3,5,7,9);

tab2: array (1..n) of Integer:= (1=>17, 3=>34,

others => 0);


Opérations sur les tableaux

• APL: langage procurant le plus d'opérations pour manipuler les scalaires, les vecteur et les matrices (e.g. inverser les colonnes d'une matrices)

• Ada permet l'effectation et la concatenation de tableaux.

• En Fortran, les opérations arithmétiques et logiques sont surchargées pour les tableaux de toutes dimensions et tailles.– Par exemple l'opérateur + appliqué à deux tableaux

effectue l'addition composante par composante.

• C, C++, Java, C#: aucune opération élémentaire• Java, C++, C#: via les méthodes.• Perl: affectation mais pas de comparaison


Matrices régulières et irrégulières

• Une matrice est régulière (ou rectangulaire) si toutes ses lignes et toutes ses colonnes ont le même nombre d'éléments

• Une matrice est irrégulière (jagged) si le nombre d'éléments est variable d'une ligne à l'autre– Possible lorsque les matrices sont

implémentées comme des tableaux de tableaux.


Tranches

• Une tranche est une sous-structure de tableau; il s'agit d'un mécanisme permettant de référencer une partie de tableau comme s'il s'agissait d'un tout.

• Uniquement utile dans les langages où les tableaux peuvent être manimulé comme des entités élémentaires.


Exemple de tranches en Fortran 95Integer, Dimension (10) :: VectorInteger, Dimension (3, 3) :: MatInteger, Dimension (3, 3, 4) :: Cube

Vector (3:6) est un tableau de 4 éléments


Exemple de tranches en Fortran 95


Implémentation des tableaux

• Une fonction d'accès transforme l'indice en une adresse en mémoire.

• Pour un vecteur:

adresse(list[k]) = adresse(list[m]) + (k-m)T = (adresse(list[m]) - mT ) + kT

où – m est l'indice minimal– T est la taille des éléments


L'accès aux tableaux multi-dimensionnels

• La mémoire étant linéaire, on doit ordonner les éléments du tableau linéairement.

3 4 76 2 51 3 8

• Deux façons courantes:– Ordonné selon les lignes – Utilisé dans la plupart des

langages:3 4 7 6 2 5 1 3 8

– Ordonné selon les colonnes – Utilisé en Fortran:3 6 1 4 2 3 7 5 8


Trouver un élément dans un tableaux multi-dimensionnels

Adresse(Tab[i,j]) = Adresse(tab[R,C] ) + ( (i - R)n + (j - C) ) * T= Adresse(tab[R,C])-(Rn+C)*T + (i*n+j)*T

où• R est l'indice de ligne minimal• C est l'indice de colonne minimal• n est le nombre d'éléments par ligne• T est la taille des éléments


Descripteur de tableauRequis pour:

• calculer la fonction d'accès en cours d'exécution• vérifier les bornes• lorsque les attributs sont dynamiques


Tableaux associatifs

• Collection non ordonnée d'éléments indexés par un nombre égal de valeurs appelées clefs. – Contrairement aux tableaux ordinaire, les

clefs doivent être conservées en mémoire

• Donc un tableau associatifs est un ensemble de paires (clef, élément)

• Présent dans Perl, Python, PHP et Ruby• Considération de conception: Forme que

prend la référence aux éléments


Les tableaux associatifs en Perl

• Le nom commence avec %%hi_temps = ("Mon" => 77, "Tue" => 79,

“Wed” => 65, …);

• On utilise les accolades pour accéder à un élément$hi_temps{"Wed"} = 83;

• Les éléments peuvent être enlevés avec deletedelete $hi_temps{"Tue"};


Les enregistrements

• Un enregistrement est un agrégat hétérogène d'éléments identifiés par un nom.

• Considérations de conception:– Quelle forme prend l'accès aux différents

champs? – Les références elliptiques sont-elles permises?


Définition d'un enregistrement en Cobol

01 EMP-REC. 02 EMP-NAME. 05 FIRST PIC X(20). 05 MID PIC X(10). 05 LAST PIC X(20). 02 HOURLY-RATE PIC 99V99.

• Remarque: En Cobol il n'est pas possible de définir un nouveau type.


Définition d'un enregistrement en Ada

type Emp_Name_Type is recordFirst: String (1..20);Mid: String (1..10);Last: String (1..20);

end record;

type Emp_Rec_Type is recordEmp_Name: Emp_Name_Type;Hourly_Rate: Float;

end record;

Emp_Rec: Emp_Rec_Type;


Références aux enregistrements

• La plupart des langages utilisent la notation avec le point

Emp_Rec.Name

• Référence complète (Fully qualified references) inclue tous les nom d'enregistrements– FIRST OF EMP-NAME of EMP-REC

• Référence elliptique permet d'omettre certains noms d'enregistrement lorsque cela ne cause pas d'ambiguïté– Exemple en COBOL:FIRST, FIRST OF EMP-NAME, et FIRST of EMP-REC sont des références elliptiques au champs FIRST de EMP-REC


Opérations sur les enregistrements• L'affectation est souvent disponible

lorsque les types sont identiques.• Ada permet la comparaison des

enregistrements• COBOL: opérateur MOVE CORRESPONDING

– Copie les champs d'un enregistrement dans les champs correspondant d'un autre

– Deux champs correspondent s'il ont le même nom


Évaluation et comparaison avec les tableaux

• Conception simple et sécure• Les enregistrements sont utilisés pour contenir

des collections d'éléments hétérogènes• L'accès est plus rapide que pour les tableau car

les noms de champs sont statique alors que les indices de tableau sont dynamiques.

• Des indices dynamiques pourraît être utilisés avec les enregistrements mais cela serait plus lent et ne permettrait pas la vérification de types.


Implémentation des enregistrements

On associe à chaque champs un décalage relatif à l'adresse du début de l'enregistrement.

Aucun descripteur n'est nécessaire durant l'exécution.

Descripteur pour la compilation


Les unions

• Une union est un type usager dont les variables peuvent stocker différents types de valeurs durant l'exécution.

• Considération de conception – Doit-on vérifier les types (de façon

dynamique)?– Doit-on les implémenter à l'aide des

enregistrements?


Unions libres

• Fortran, C, and C++: pas de support pour la vérification de types. Ce type d'union est appelé union libre.

• Le code C suivant est valide:union flexType{

int entier;float reel;

} monUnion;float x;...monUnion.entier=27;x=monUnion.reel;


Unions discriminées

• Pour avoir vérification de types il est nécessaire qu'à chaque variable de type union soit associé un indicateur de type appelé discriminant (tag)– Supporté par Ada


Les unions en Ada

type Shape is (Circle, Triangle, Rectangle);type Colors is (Red, Green, Blue);type Figure (Form: Shape) is record

Filled: Boolean;Color: Colors;case Form is

when Circle => Diameter: Float;when Triangle =>

Leftside, Rightside: Integer;Angle: Float;

when Rectangle => Side1, Side2: Integer;end case;

end record;


Les unions en Ada (suite)

• Variable sans contrainte; le type peut être donné plus tard: Figure_1: Figure;Figure_1 := ( Filled=>True,

Color=>Blue,Form => Rectangle,Side_1=>12,Side_2=>3);

• La variable est contrainte à être un triangle; le type ne peut plus être changé.Figure_2: Figure(Form=>Triangle);


Illustration des unions en Ada


Évaluation des unions

• Potentiellement non sécure– Une des raisons pour laquelle C, C++ et

Fortran ne sont pas fortement typé

• Java et C# ne supportent pas les unions– Réflète le soucis croissant de sécurité dans les

langages de programmation


Les pointeurs et les références

• Une variable de type pointeur est une variable dont la valeur est une adresse mémoire ou la valeur nil

• Permet d'utiliser la puissance de l'adressage indirect

• Permet de gérer l'allocation dynamique de la mémoire


Considérations de conception des pointeurs

• Quelle est la portée et la durée de vie d'un pointeur?

• Quelle est la durée de vie d'une variable dynamique sur le tas?

• Les pointeurs sont-ils contraints à pointer des valeurs de type précis?

• Les pointeurs sont-ils utilisés pour l'allocation dynamique de la mémoire, l'adressage indirect, ou les deux?

• Le langage supporte-il les pointeurs, les références, ou les deux?


Opérations sur les pointeurs

• Deux opérations fondamentales: l'affectation et l'indirection (ou déréférence)

• L'affectation est utilisée pour mettre une adresse utile dans un pointeur

• L'indirection donne la valeur stockée dans la case mémoire dont l'adresse se trouve dans le pointeur– L'indirection peut être implicite ou explicite– C++ utilise seulement l'indirection explicite via *

j = *ptr

met dans j la valeur se trouvant à l'adresse contenue dans ptr


Illustration d'une affectation

Opération j = *ptr


Problèmes avec les pointeurs

• Pointeurs en suspens (dangling pointers)– Un pointeur contient l'adresse d'une case

mémoire ayant été désallouée.

• Variables anonymes perdues– Une variable dynamique sur le tas n'est plus

accessible alors qu'elle n'a pas été désallouée (en anglais: garbage)

• Exemple en C

int *pt;pt = new int;*pt=0;pt = new int;*pt =1;


Les pointeurs en Ada

• Les pointeurs sont appelés access en Ada type ptr_Integer is access Integer; ptr : ptr_Integer;

ptr.all = 999;• Le problème des pointeurs en suspens est

diminué par le fait qu'une variable dynamique peut être automatiquement désallouée lorsque l'on sort de la portée de son type.

• Peu de compilateurs implémentent cette option• Le problème des variables anonymes perdues

n'est pas éliminé• Indirection implicite et pas d'adressage indirect


Les pointeurs en C et C++

• Extrèmement flexibles mais dangereux• Les pointeurs peuvent pointer à n'importe quelle

adresse sans égard à leur validité• Utilisés pour l'allocation dynamique de la

mémoire et pour l'indirection• Arithmétique des pointeurs possible• Opérateurs d'adressage et d'indirection

(indirection explicite) • Un pointeur générique void * peut pointer sur

n'importe quel type mais ne peut pas être déréférencé (évitant ainsi le problème de vérification de type).


L'arithmétique des pointeurs en C et C++

float stuff[100];float *p;p = stuff;

*(p+5) est équivalent à stuff[5] et p[5]*(p+i) est équivalent à stuff[i] et p[i]


Les pointeurs en Fortran 95

• Peut pointer sur le tas ou la piles• Indirection implicite• Les pointeur ne peuvent pointer que sur les

variables définies avec l'attribut TARGET :INTEGER, TARGET :: T

INTEGER, POINTER :: P P => T

Y = 2 * P• Les pointeurs peuvent aussi pointer sur des

variables anonymes :FLOAT, POINTER :: FPALLOCATE(FP)FP = 3.1416


Les références

• C++ inclu un type de pointeurs particuliers appelés références.

• Utilisées principalement pour le passage des paramètres

• Java extensionne les références du C++ et les utilise pour remplacer complètement les pointeurs.

• C# inclu à la fois les références de Java et les pointeurs de C++


Évaluation des pointeurs

• Deux problèmes importants: pointeurs en suspens et variables anonymes perdues

• On compare souvent les pointeurs au goto: – Le goto élargie l'intervalle des instructions

pouvant être exécuter à l'étape suivante.– Les pointeurs élargissent l'intervalle de cases

mémoire pouvant être accédée par une variable

• Les pointeurs ou les références sont nécessaires aux structures de données dynamiques: difficile de s'en passer.


Le problème des pointeurs en suspens

• Tombstone: On utilise un pointeur intermédiaire– Un pointeur ne pointe que sur un tombstone

qui, à son tour, vaut nil ou pointe sur une variable anonyme (dynamique sur tas).

– Lors d'une désallocation, on ne fait que mettre le tombstone à nil.

– Couteux en espace et en temps.


Le problème des pointeurs en suspens

. Locks-and-keys: La valeur d'un pointeur est représentée par une paire (clef, adresse)– Une variable dynamique sur tas contient un champs

contenant une valeur de verrou (lock value).– Lors de l'allocation d'une variable anonyme, une valeur

de verrou est créée et affectée dans la clef du pointeur. – Les pointeurs voulant accéder à cette variable doivent

avoir une clef correspondant à la valeur de verrou.– Lors de la désallocation, la valeur de verrou est

remplacée par une valeur illégale.– Utilisé dans UW-Pascal (université du Wisconsin)


Gestion de la mémoire

• Processus très complexe (en particulier lorsque la désallocation est implicite).

• Considérons d'abord des cases mémoire de taille fixe.

• Deux approches:– Méthode du compteur : approche graduelle– Récupération de mémoire (garbage

collection): On récupère la mémoire disponible lorsqu'il n'y en a presque plus.


Méthode du compteur

• Pour chaque variable anonyme on conserve le nombre de pointeurs y faisant référence.

• Désavantages: – augmente l'espace requis– augmente le temps d'exécution – complications pour les listes circulaires


Récupération de mémoire

• Le moteur d'exécution (run-time system) alloue l'espace mémoire demandé et dissocie au besoin les pointeurs des cases mémoires

• Lorsqu'il n'y a plus sufisamment d'espace libre, la récupération de mémoire débute:– Chaque case mémoire a un bit indiquant son

utilisation – On initialise chaque bit à 0 (garbage)– On parcoure tous les pointeurs pour marquer à 1 les

cases utilisées– Toutes les cases encore à 0 sont retournées dans la

liste des cases disponibles

• Désavantage: Prend beaucoup de temps (particulièrement lorsque le programme utilise beaucoup d'espace).


Algorithme de marquage

La ligne pointillée indique l'ordre de marquage des noeuds


Cases mémoire de taille variable

• Ajoute à la difficulté• Requis par la plupart des langages• Problèmes additionnels pour la

récupération de mémoire– L'initialisation des cases à 0 est plus difficile– Le processus de marquage se complique car

les pointeurs ne sont plus à des positions fixes dans les cases.

– La maintenance d'une liste des cases disponibles devient non trivial (même lorsque que la désallocation est explicite)


Sommaire

• Les types de données sont pour une large part ce qui détermine le style et l'utilité d'un langage

• Les types élémentaires de la plupart des langages impératifs incluent: les types numériques, les caractères et les booléens.

• Les types intervalle et les énumérations ajoutent à la facilité d'écriture, la lisibilité et la fiabilité des langages

• Les tableaux et enregistrements font partie de la plupart des langages

• Les pointeurs sont utilisés pour l'adressage indirect ainsi que pour l'allocation dynamique de la mémoire.

• Les principaux problèemes causés par l'utilisation des pointeurs sont: les pinteurs en suspend et les variables anonymes perdues.

Documents

ISBN 0-32149362-1 Chapitre 6 Types de données. Copyright © 2007 Addison-Wesley. All rights reserved.1-2 Chapitre 6: Sujets Introduction Types de données