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