CSI 3525 - Groupe
de discussion #9
Questions et exercices
1. Enumerer les principaux attributs associes a une variable. On donnera
une definition precise de chaque attribut et quelques problemes s'y rapportant.
Une variable est une abstraction pour une case memoire ou une collection
de cellules de memoire. Bien que pour le programmeur, elle se reduise le
plus souvent a un nom representant une valeur, on peut la caracteriser
completement avec les attributs suivants:
-
nom: il s'agit de l'identifiant de la variable. Des problemes classiques
lies aux noms sont le nombre et la diversite des caracteres utilisables,
la sensibilite aux minuscules/majuscules et les mots cles/mots reserves.
-
adresse: association a un emplacement de la memoire, appelee aussi l-valeur.
Problemes: references locale et absolue a une variable, alias (et donc
pointeurs)...
-
valeur: il s'agit du contenu de la case memoire ou r-valeur. Problemes:
taille de la case memoire necessaire (lien au type), alias...
-
type: intervalles de valeurs que la variable peut prendre. Problemes: precision,
codage des entiers/des reels...
-
duree de vie: temps pendant lequel la variable est lie a un emplacement
memoire. Problemes: difference avec la portee, classification des variables
(cf question suivante)...
-
portee: intervalle d'instructions pendant lequel la variable est visible
(c'est-a-dire concretement utilisable par une instruction). Problemes:
portees statique/dynamique (voir exercices), notion de blocs logiques...
2. Expliquer et detailler la classification des variables selon leur duree
de vie faite dans le livre.
On peut distinguer quatre categories de variable sur le critere de la duree
de vie:
-
Variables statiques: elles sont associes a leur emplacement memoire au
moment de la compilation. Elles sont souvent globales et ont une memoire,
c'est-a-dire que leur valeur n'est pas ecrasee entre deux executions d'un
sous-programme. Ce type d'association est efficace et permet de gagner
du temps a l'execution mais interdit de nombreux aspects de la programmation
dynamique, dont la recursion.
-
Variables a pile dynamique: ces variables ont un type determine statiquement
mais l'association memoire est retarde au moment de la declaration. C'est
le mode utilise par defaut dans la plupart des langages imperatifs. Ceci
permet de faire de la recursion et d'economiser par allocation/desallocation
de l'espace memoire. La contre-partie est que le temps d'execution en est
rallonge.
-
Variables a tas dynamique explicites: l'allocation et la desallocation
de la variable sont faites explicitement par le programmeur. Le type
en revanche est connu au moment de la compilation. La valeur de la variable
est stockee dans le tas, qui est l'espace memoire utilise durant l'execution.
Un avantage est qu'elles sont pratiques a manipuler, un inconvenient est
que le tas etant assez desorganise, une erreur de manipulation peut entrainer
des effets de bord causant des bugs difficiles a detecter.
-
Variables a tas dynamique implicites: elles sont tres flexibles car l'allocation
memoire n'est effectuee qu'au moment de leur instanciation. Elles possedent
les memes inconvenients que les precedentes et sont encore plus gourmandes
en temps au moment de l'execution puisque tout est determine de maniere
dynamique.
3. Definir le controle de type. En particulier, mettre en evidence les
compromis realises dans la conception d'un langage entre le controle et
la flexibilite.
Le controle de type consiste a verifier que les types d'une operation (au
sens large, y compris sous-programmes et assignations) et de ses operandes
sont compatibles. Eventuellement, la compatibilite necessite une conversion,
on parle de contrainte.
Le controle de type est statique ou dynamique suivant le moment du
lien entre les variables et leur type. Bien entendu, le controle de type
dynamique augmente d'autant plus le temps d'execution. Si le type d'une
variable peut changer lors du deroulement du programme, la detection de
toutes les erreurs de type ne peut se faire que de facon dynamique.
On parle de typage fort lorsque toutes les erreurs de type sont detectees.
Ceci permet evidemment de detecter et corriger bon nombre de bugs, a la
compilation ou a l'execution. Peu de langages sont parfaitement fortement
types: Ada en fait partie (si l'on excepte l'existence d'une instruction
de suspension de controle de type mise en evidence dans le livre). Le resultat
est qu'Ada est tres fiable, un programme qui compile a de bonnes chances
de realiser ce qu'a desire le programmeur car on est assure que toutes
les fonctions recoivent des arguments du type demande. Cependant, la contre-partie
est que nous perdons en flexibilite, c'est a dire que, meme lorsque nous
savons qu'une instruction va imposer une contrainte et que c'est ce que
nous voulons faire, le compilateur va l'interdire. Un exemple de ce type
de probleme est la conversion entiers/flottants ou de facon plus extreme
la conversion chaine de caracteres/nombres. Ainsi Perl est un langage tres
faiblement type. Dans un langage faiblement type, la liberte est plus grande
mais il est aussi de la responsabilite du programmeur de verifier que chaque
instruction correspond effectivement a ce qu'il veut faire.
4. Exercice 8 p 214
Portee statique.
i. sub1: declaration sub1.
ii. sub2: declaration sub1.
iii. sub3: declaration main.
Portee dynamique.
i. sub1: declaration sub1.
ii. sub2: declaration sub1.
iii. sub3: declaration sub1.
5. Exercice 11 p 215
sub1: a, y, z locaux, x main
sub2: a, x, w locaux, y,z main
sub3: a, b, z locaux, x, w sub2, y main
6. Exercice 14 p 217
a.
y defini sub1,
b, z defini sub2,
a, x, w defini sub3.
b.
y, z defini sub1,
a, x, w defini sub3.
c.
b defini sub2,
x, w defini sub3,
a, y, z defini sub1.
d.
x, w defini sub3,
a, y, z defini sub1.
e.
y defini sub1,
x, w defini sub3,
a, b, z defini sub2.
f.
x, w defini sub3,
b defini sub2,
a, y, z defini sub1.
Remarque: les variables x, y et z de main ne sont jamais visibles dans
les cas ci-dessus.
7. Presenter les avantages et inconvenients des quatre methodes de stockage
des tableaux introduites dans le livre.
Un tableau est une structure de donnees regroupant (et indexant) des elements
de meme type. On peut voir un tableau comme une application de l'ensemble
des valeurs que peut decrire l'index (typiquement un nombre fini d'entiers)
vers l'ensemble du type considere.
-
Dans un tableau statique, les bornes de l'index ainsi que le contenu du
tableau sont connus avant l'execution. Ce type d'element permet donc de
gagner du temps a l'execution mais fournit moins de flexibilite.
-
Dans un tableau fixe a pile dynamique, les bornes de l'index sont fixees
statiquement mais l'allocation memoire est realisee au moment de l'execution.
L'avantage est que cela permet d'economiser de la memoire puisque l'allocation
n'est necessaire que pendant la duree de vie du tableau.
-
Dans un tableau a pile dynamique, les bornes de l'index et l'allocation
memoire sont effectuees dynamiquement pendant l'execution (mais restent
fixes pendant la duree de vie de la variable). L'avantage est la flexibilite: la
taille du tableau n'a pas etre connu par le programmeur lorsqu'il ecrit
la declaration.
-
Dans un tableau a tas dynamique, les bornes de l'index et l'allocation
memoire peuvent etre redefinis autant de fois que necessaire pendant l'execution.
Ainsi l'utilisateur peut utiliser les tableaux de facon tres pratique.
En revanche, le temps d'execution est plus important.
8. Definir le type Union et expliquer les problemes qui y sont lies et les
facons de les resoudre.
Le type Union n'est pas un type a proprement parler mais une facon de stocker
dans le meme emplacement des variables de type different. Ceci peut etre
utile par exemple pour initialiser et maintenir une table de constantes
relatif a un programme donne dans un compilateur: ce serait une enorme
perte de place que de faire une table pour les constantes entieres, une
table pour les constantes flottants, une table pour les chaines de caracteres,
etc... Sans aller aussi loin, dans des langages fortement types, il arrive
souvent que l'on ne connaisse pas le type d'une variable au moment de la
compilation et cela peut etre genant (definir un nouveau type est parfois
lourd et inutile).
Les problemes qui se posent sont bien evidemment de faire du controle
de type et de permettre des operations plus complexes sur les operandes
de type Union. Une facon de faire du controle de type est de doter chaque
variable de type Union d'une etiquette mentionnant son type actuel. Le
probleme est que si l'etiquette est modifiable librement par l'utilisateur,
rien ne garantit qu'elle va rellement decrire ce qui est dans la variable
si le programmeur fait une erreur dans son programme et l'utilisation d'etiquettes
rajoute de la complexite et pas beaucoup de fiabilite. Donc en general,
le controle de type est laisse de cote pour des variables de type Union.
Ada fournit une solution extremement fiable mais aussi tres contraignante
pour l'utilisateur en imposant le systeme d'etiquette pour toute variable
de type Union.
Retenons que la manipulation du type Union est extremement risquee
dans la plupart des langages car les compilateurs detectent tres peu d'erreurs
sur ces types. Cela dit, ils sont parfois tres pratiques mais doivent etre
utilises a bon escient.
9. Expliquer ce qu'est un pointeur et presenter les operations basiques sur
les pointeurs.
Un pointeur est une variable contenant une adresse memoire ou une valeur
speciale, le pointeur nul. Les pointeurs sont particulierement utiles pour
l'allocation dynamique (sur le "tas"). Ils different des variables classiques
en cela qu'ils sont de type moins structure et qu'ils sont lies au type
de la variable dont ils designent l'adresse.
Il n'y a bien sur pas d'operations arithmetiques classiques sur les
pointeurs (l'addition ou la multiplication de deux adresses n'a en general
aucun sens). Une operation est l'assignation: il s'agit d'allouer
une adresse au pointeur. En general, l'assignation est faite au moment
de l'initialisation du pointeur.
Bien que l'on puisse utiliser la variable designee par le pointeur
tout a fait normalement, une autre operation est specifique au pointeur:
la dereferenciation. Il s'agit simplement d'obtenir explicitement l'adresse
sur laquelle le pointeur est dirigee et non pas la valeur contenue dans
cette adresse (c'est en fait la valeur contenue dans le pointeur !). Ce
type d'operation est utile lorsque l'on veut par exemple initialiser un
pointeur sur la meme adresse qu'un pointeur existant (on utilise * en C/C++).
10. Exercice 13 p 278
Il y a bien sur plusieurs methodes et la question est suffisamment large
pour que l'on puisse envisager des manieres diametralement opposees d'y
repondre. En voici deux:
- Tolerer une ecriture comme celle qui est proposee dans l'enonce mais rajouter
au moment de la compilation une etiquette pour chaque constante d'un type
enumere contenant son type precis. Cette etiquette sera remplie par le compilateur
en fonction du contexte dans lequel est utilisee la variable. Evidemment,
il faut que le contexte permettent de discriminer simplement (mais si ce n'est
pas le cas cela veut dire qu'un lecteur humain n'y arriverait pas non plus
et on ne peut donc pas exiger cela d'un compilateur).
- Utiliser le meme systeme d'etiquette mais exiger qu'il soit rempli par
l'utilisateur a chaque reference a une constante ambigue. Ainsi, il devra
utiliser colors.blue pour designer la couleur et mood.blue pour designer l'humeur.
Cette methode est beaucoup plus facile a implementer que la precedente mais
est aussi plus penible pour l'utilisateur.
rigouste@site.uottawa.ca