Portee des identificateurs et environnements

Dans tout langage de programmation, il existe differentes constructions permettant d’introduire des variables. Ce sont par exemple la definition de fonctions et l’ouverture d’un bloc. On appelle de telles constructions des lieurs de variables.
Le sens des variables qui figurent dans les expressions ou les instructions d’un programme doit toujours ˆetre interpr´et´ par rapport a` leur introduction c’est-a`–dire que l’on doit toujours ˆetre capable de rattacher une utilisation de variable a` son lieur pour pouvoir l’interpr´eter correctement.
Ce n’est pas toujours ´evident car plusieurs variables d’un programme peuvent avoir le mˆeme nom. Un mˆeme identificateur peut ˆetre utilis´e par exemple pour un param`etre de fonction et pour une variable locale d´eclar´ee dans un block `a l’int´erieur du corps de la fonction, et ceci éventuellement avec des types diff´erents.
La plupart des langages de programmation utilisent la mˆeme r`egle pour relier une occurence de variable a` son lieur et cette r`egle est tr`es facile a` expliquer sur l’arbre de syntaxe abstraite. Pour rattacher une utilisation de variable a` son lieur, il suffit de remonter la branche de l’arbre sur laquelle se trouve l’occurence de variable jusqu’`a trouver un lieur qui d´efinit cette variable. Le premier trouv´e est le bon. En d’autres termes, c’est le lieur le plus proche, c’est-a`-dire celui qui a introduit en dernier la variable, qui est a` utiliser. La port´ee d’un lieur est le sous-arbre dont il est la racine sauf que, a` l’int´erieur de ce sous-arbre peuvent apparaˆıtre d’autres lieurs cachant certaines liaisons que le premier a introduites.
Pour g´erer cette relation entre une utilisation de variable et son introduc-tion, nous utiliserons la notion d’environnement. Un environnement peut ˆetre vu comme une table qui associe a` toute variable introduite une ou plusieurs propri´et´es, par exemple, son type ou bien sa valeur. Le fait de relier une utilisation de variable a` sa d´efinition la plus proche permet de g´erer les environnement comme des piles. Nous expliquerons cette gestion en consid´erant pour le moment des environnements de typage, c’est-a`-dire des environnement o`u les variables sont associ´ees a` leur type.
– Pour construire l’environnement de typage valable en un point du pro-gramme, on parcourt la branche qui va de la racine de l’arbre de syntaxe abstraite a` ce point. On part avec un environnement vide et chaque fois qu’on traverse un lieur, on empile les liaisons introduites par ce lieur.
– Pour connaitre le type d’une occurence de variable, on prend l’environne-ment de typage correspondant a` cette occurence et on le parcourt depuis le sommet de pile jusqu’`a trouver la premi`ere liaison de la variable. Cette liaison indique le bon type. Si on ne trouve pas de liaison dans l’environ-nement, c’est que la variable est utilis´ee sans avoir et´ introduite, ce qui est une erreur.
Par exemple, dans le programme pascal suivant
function f(m:integer, n:integer): integer;
begin
function g(n:boolean,p:integer):integer;
begin if n then g:=m+p else g:=m*p end
m:integer;
m:=7;
f:= g(true,m+n)
end
l’environnement correspondant a` l’instruction
if n then g:=m+p else g:=m*p
est [p:integer;n:boolean; n:integer; m:integer] (en pla¸cant le haut de pile `a gauche)
et l’environnement correspondant `a l’instruction f:= g(true,m+n) est [m:integer; n:integer; m:integer].
Le probl`eme de port´ee des identificateurs est assez simple en ce qui concerne le typage mais il peut ˆetre nettement plus complexe quand on consid`ere l’ex´ecution des programmes. Par exemple, l’ex´ecution de l’appel de fonction f(2,3) o`u la fonction f est celle d´efinie plus haut rend la valeur 12 et non pas, comme on pourrait le croire, la valeur 17. En effet, bien que la valeur de la variable m courante soit 7 au moment de l’appel g(true, m+n), ce qui revient donc `a ´evaluer g(true,10), la variable m utilis´ee dans le corps de la fonction g vaut 2 car cette variable m est le param`etre m dans la fonction f et non pas la variable m qui a et´ introduite dans le corps de la fonction f post´erieurement `a la d´efinition de g.
Si on y r´efl´echit, cette interpr´etation de la variable m dans le corps de g est la seule qui soit raisonnable car la nouvelle variable m introduite dans le corps de f aurait parfaitement pu avoir un type diff´erent de integer. Si on veut que le typage garantisse l’absence d’erreur de type `a l’ex´ecution, il est indispen-sable que l’ex´ecution ne remette pas en cause la validit´e des environnements utilis´es pour le typage. Cete d´efinition de la port´ee des identificateurs est connue sous le nom de port´ee statique. Elle est utilis´ee dans la plupart des langages sauf dans certaines versions anciennes de lisp et aussi, pour ce qui est des m´ethodes, dans les langages a` objects.
La port´ee statique des identificateurs ne pose pas de probl`eme d’implanta-tion dans les langages qui n’autorisent pas l’emboitement des d´efinitions de fonctions comme c et ses d´eriv´es ou java. Par contre, pour les autres elle implique soit une compilation d´elicate des acc`es au variables (par exemple en pascal avec la notion de display) soit l’utilisation de fermetures pour repr´esenter les fonctions comme en caml ou en scheme.

Les types

Typage statique et typage dynamique

Le syst`eme de types d’un langage de programmation refl`ete la nature des structures de donn´ees fournies par ce langage et permet un contrˆole sur l’utilisation correcte de ces donn´ees. Ce contrˆole est surtout utile s’il s’exerce a` la compilation c’est-a`-dire avant l’ex´ecution des programmes. Il permet alors de d´etecter un certain nombre d’erreurs de programmation qui, sans cela, conduiraient a` des erreurs d’ex´ecutions. Par ailleurs, lorsque le typage est v´erifi´ a` la compilation (typage statique), le code compil´e n’a pas besoin de contenir de v´erifications dynamique de types et il est donc potentiellement plus efficace.
Cependant, le typage statique introduit aussi des contraintes. Certains pro-grammes corrects peuvent ˆetre refus´es par le v´erificateur de types alors qu’ils ne produiraient pas d’erreurs a` l’ex´ecution. Certains programmes peuvent avoir des comportements dynamiques plus int´eressants si certaines d´ecisions sont prises a` l’ex´ecution et non pas a` la compilation. En particulier pour les langages a` objets, l’interpr´etation dynamique plutˆot que statique des messages est un el´ement de souplesse important.
Dans cette section, on s’int´eressera uniquement au typage statique. Les as-pects dynamiques seront abord´es dans la section 1.5.

Les garanties apport´ees par le typage statique

On dira qu’un langage de programmation est fortement typ´e si l’accep-tation d’un programme par le compilateur garantit l’absence d’erreurs de types `a l’ex´ecution.
C’est loin d’ˆetre le cas pour tous les langages typ´es. Il s’agit d’une propr´et´ id´eale dont les langages r´eels sont souvent fort eloign´es. En particulier le lan-gage c, qui autorise de nombreuses conversions de types hasardeuses, est loin de satisfaire ce crit`ere. Une victime c´el`ebre de ces conversions hasardeusse est la fus´ee Ariane 5 dont le premier vol a echou´ `a cause d’une conversion sur 16 bits d’un entier 32 bits.
Les autres langages offrent plus de garanties. En particulier c++ apporte beaucoup plus de garanties que c dans ce domaine. Une exp´erience int´eressante consiste a` prendre un logiciel ´ecrit en c et a` le recompiler avec le compila-teur c++. On d´etecte alors en g´en´eral des conversions implicites que c++ n’accepte pas a` juste raison. Cependant, le b´en´efice apport´e par c++ est en partie perdu si le programme force les conversions par des casts explicites. Les langages caml et java se rapprochent beaucoup plus de langages forte-ment typ´es mais ils ont aussi certaines failles. Le typage de caml ne prend pas en compte les exceptions et donc, un programme correctement typ´e peut engendrer une exception non rattrap´ee sans que cela se voie au typage. Par ailleurs, ces langages autorisent par souci d’interop´erabilit´ l’utilisation de modules externes ´ecrits en assembleur ou en c qui n’offrent pas de garanties de typage. Au moins, ces langages offrent-ils un noyau fortement typ´e.
En pratique, pour effectuer des v´erifications qui ne sont pas faites au ty-page, on peut ajouter une phase d’analyse statique qui v´erifie des propri´et´es importantes comme le respects des bornes des tableaux et la correction des conversions de types.

Les types predefinis

Dans tous les langages, il existe des types pr´ed´efinis correspondant a` diff´e-rentes sortes de nombres et en g´en´eral aux valeurs bool´eennes, aux caract`eres et aux chaˆınes de caract`eres. A ces types sont associ´ees des constantes telles que 13, 3.14, true, ’a’, « hello » qui sont utilisables directement dans les programmes.

Les constructeurs de types predefinis

Il existe aussi des constructeurs de types tels que pointeur (pointer) ou tableau (array). Ces constructeurs ne sont pas directement des types en eux-mˆeme mais ils permettent de construire des types quand on les applique `a un type de base (ou `a plusieurs types de base).
La fa¸con dont on note les types construits `a l’aide de constructeurs de types varie suivant les langages. En pascal, le type “pointeur sur entier” se note (^integer) et en caml (int ref). En c, il n’y a pas v´eritablement de d´enotation pour un tel type mais plutˆot une syntaxe pour d´eclarer une variable p de ce type par int *p;.
Cependant, au niveau de la syntaxe abstraite, il est n´ecessaire d’avoir une d´enotation pour chaque type. C’est la raison pour laquelle, nous avons in-troduit dans notre syntaxe abstraite de c, le constructeur PtrType a` un argument, ce qui permet de noter PtrType(IntType) le type “pointeur sur entier”.
La d´eclaration d’une variable de type tableau d’entier peut aussi prendre des formes assez vari´ees selon le langage utilis´e.
En pascal, les bornes du tableau, et par cons´equent, sa taille, font partie du type, mˆeme lorsqu’il s’agit du type d’un param`etre de proc´edure ou de fonction :
tab: array 1..100 of integer;
function sumarray(t: array 1.100 of integer):integer;
En c et dans ses d´eriv´es, la taille d’un tableau est n´ecessairement indiqu´ee lorsque le tableau est allou´e statiquement. Par contre, le tableau est pass´e en param`etre, cette information n’est pas exig´ee et elle n’est pas disponible au cours des calculs. On est alors amen´ `a utiliser un deuxi`eme param`etre pour passer la taille du tableau :
int tab[100];
int sumarray(int t[], int size);
En java et en caml, la taille du tableau ne fait pas partie du type mais elle intervient lorsqu’on construit (alloue) le tableau et elle est disponible au cours des calculs.
Il est donc naturel de consid´erer dans le cas de c, java ou caml, que ta-bleau est un constructeur `a un argument comme nous l’avons fait plus haut dans la syntaxe abstraite de c avec le constructeur ArrayType. Pour la syn-taxe abstraite de pascal, on devrait plutˆot consid´erer que le constructeur ArrayType a deux arguments, un pour le type des el´ements du tableau et un autre pour le type intervalle qui d´efinit ses bornes.
En fait, ce qu’il est important de retenir, c’est que les constructeurs de type fournissent le moyen d’introduire dans un langage de programmation une infinit´e de types qui sont obtenus en appliquant les constructeurs de type aux types de base et aussi aux types qui sont eux-mˆemes construits de cette fa¸con. Des exemples de tels types sont par exemple array(int) , pointer(float) ou encore array(pointer(string)) et pointer(pointer(bool)).

Les definitions de nouveaux types

Les langages traditionnels comme c ou pascal offrent essentiellement deux cat´egories de constructions pour introduire de nouveaux types. La premiere correspond `a ce qu’on appelle le produit cart´esien en math´ematique et consiste `a permettre de construire des n-uplets de valeurs c’est-`a-dire de r´eunir dans un mˆeme objet plusieurs valeurs qui peuvent ˆetre de types diff´erents. Ces constructions s’appellent des structures en c et des records (en fran¸cais enregistements) en pascal. Une structure ou un enregistrement poss`edent des champs qui contiennent des valeurs.
En pascal :
type point = record x:real; y:real end;
En c :
struct point {float x; float y;}
La deuxi`eme cat´egorie de constructions correspond `a ce qu’on appelle des sommes ou des unions disjointes en math´ematique et consiste `a r´eunir dans un mˆeme type plusieurs types pr´eexistants. Ces constructions s’appelle des unions en c et des variantes en pascal. Les variantes de pascal sont res-treintes en ce sens que les variantes portent uniquement sur certains champs d’un record et ne constituent pas une construction ind´ependante.
Il existe aussi en g´en´eral une construction pour introduire des types `a do-maine fini (énumérations).
Une fois d´efinis, ces types viennent compl´eter la liste des types pr´ed´efinis du langage et ils s’utilisent de la mˆeme fa¸con que ceux-ci dans les d´eclarations. Par ailleurs, ils peuvent ˆetre utilis´es comme arguments des constructeurs de types.

Les definitions de nouveaux constructeurs de types

Outre la d´efinition de nouveaux types, un langage comme caml permet de d´efinir aussi de nouveaux constructeurs de types. En fait, en caml, on peut utiliser une seule et mˆeme construction pour les unions, les enum´erations et la d´efinitions de nouveaux constructeurs.
Voici la d´efinition d’une enum´eration :
type couleur = Trefle | Carreau | Coeur | Pique;;
Les valeurs du type enum´er´ couleur sont Trefle, Carreau, Coeur et Pique.
Voici la d´efinition d’une union :
type num = Int of int | Float of float;;
Int et Float sont les constructeurs du type num qui est l’union du type int et du type float. Il s’agit de constructeurs de valeurs. Par exemple Int(3) et Float(2.5) sont deux valeurs du type num obtenues en appliquant respectivement le constructeur Int a` la valeur enti`ere 3 et le constructeur Float a` la valeur flottante 2.5. Notons que Trefle, Carreau, Coeur et Pique sont ´egalement des constructeurs de valeurs mais ce sont des constructeurs a` 0 argument c’est-a`-dire des constructeurs constants.
Les types sommes de caml tirent leur principal int´erˆet du fait qu’ils peuvent ˆetre r´ecursifs :
type arbre = F of int | Bin of arbre * arbre;;
On d´efinit ainsi les arbres binaires ayant des entiers aux feuilles.
Pour d´efinir un constructeur de type, il suffit de donner un ou plusieurs param`etres aux types définis. Par exemple, on peut red´efinir le type arbre de fa¸con a` ce qu’il soit param´etr´ par le type des feuilles :
type ’a arbre = F of ’a | Bin of ’a arbre * ’a arbre;;
Ici, arbre est un nouveau constructeur de type qui permet d’utiliser des types tels que int arbre ou bien string arbre ou encore int array arbre.

Le polymorphisme

On appelle polymorphisme le fait que certaines valeurs d’un langage de programmation peuvent avoir plusieurs types. Le polymorphisme peut se manifester de mani`ere tr`es diverse.
Tout d’abord, certaines valeurs sp´eciales ont naturellement plusieurs types. Par exemple, la valeur nil (ou null ) qui d´esigne souvent un pointeur vide (un pointeur qui ne pointe sur rien) poss`ede a` la fois tous les types pointeurs. De fa¸con plus int´eressante, certaines valeurs poss`edent plusieurs types parce qu’elles appartiennent a` un type qui est naturellement inclu dans un autre type. Par exemple, la valeur 3 poss`ede le type entier mais dans l’expression 3 + 2.5, elle poss`ede le type flottant car le compilateur sait la transformer en un flottant avant de r´ealiser l’addition. Ce type de polymorphisme, qui apparait de fa¸con un peu ad hoc dans la plupart des langages de program-mation se trouve syst´ematis´ de fa¸con plus rigoureuse dans les langages a` objets. Si B est une sous-classe de A, alors tout objet de classe B peut aussi ˆetre consid´e comme un objet de classe A. Nous reviendrons sur ce point qui m´erite un examen d´etaill´ dans la section 1.3.9.
Le polymorphisme peut aussi se manifester au niveau des fonctions ou bien des m´ethodes des langages a` objets et c’est a` ce niveau-l`a qu’il est le plus int´eressant. Une fonction (ou une proc´edure, ou une m´ethode) sera dite po-lymorphe si elle peut ˆetre appliqu´ee (ou envoy´ee s’agissant de m´ethodes) a` des objets de types diff´erents. L’int´erˆet de ce polymorphisme tient au fait qu’il donne aux programmes utilisant cette fonction ou cette m´ethode des possibilit´es d’utilisation plus large puisqu’il peut s’appliquer a` diff´erents types de donn´ees. Consid´erons par exemple une proc´edure qui inverse l’ordre des el´ements d’un tableau. Il s’agit d’une proc´edure qui peut ˆetre appliqu´ee a priori a` tous les tableaux, quelle que soit la nature des el´ements du ta-bleau. Cependant, dans un langage typ´e non polymorphe, il est impossible d’´ecrire une telle proc´edure car on doit indiquer le type du tableau pass´e en param`etre. Une telle proc´edure est un exemple typique de ce qu’on ap-pelle le polymorphisme param´etrique dans lequel un mˆeme code peut ˆetre appliqu´ee a` des donn´ees de types diff´erents. Cette forme de polymor-phisme est a` distinguer de la surcharge qui consiste a` donner un mˆeme nom a` des proc´edures diff´erentes qui r´ealisent des des traitements plus ou moins similaires sur des donn´ees diff´erentes. Les langages a` objets offrent une syst´ematisation de cette notion de surcharge.
Nous examinerons s´epar´ement ces deux formes de polymorphisne.

1 Diversité des langages 
1.1 Les niveaux de syntaxe
1.1.1 La syntaxe concrˆete
1.1.2 La syntaxe abstraite
1.1.3 Description de la syntaxe abstraite
1.1.4 Les generateurs d’analyseurs syntaxiques
1.2 Port´ee des identificateurs et environnements
1.3 Les types
1.3.1 Typage statique et typage dynamique
1.3.2 Les garanties apport´ees par le typage statique
1.3.4 Les constructeurs de types pr´ed´efinis
1.4 L’´evaluation 
1.4.1 La compilation
1.4.2 La compilation vers une machine virtuelle
1.4.3 L’interpr´etation
1.4.4 Les diff´erents aspects de l’´evaluation
1.5 Les environnements d’execution 
1.5.1 Gestion dynamique de la m´emoire
1.5.2 Typage dynamique
1.5.3 Interpr´etation dynamique de messages
2 Analyse syntaxique
2.1 Quelques rappels et notations
2.1.1 grammaires
2.1.2 un exemple
2.1.3 arbres de d´erivation et ambiguit´e
2.2 Analyse syntaxique montante
2.2.1 automates shift / reduce
2.2.2 exemple
2.3 Les tables d’analyse montantes 
2.3.1 FIRST et FOLLOW
2.3.2 Utilisation de FIRST et FOLLOW
2.4 Traitement des expressions arithmetiques
2.4.1 Traitement de l’ambiguit´e
2.4.2 Construction de l’automate SLR
2.4.3 Construction de la table SLR
2.5 Traitement des listes
2.6 Compl´ements
2.6.1 Propri´et´es des automates SLR
2.6.2 Limites des tables SLR
2.6.3 Automates LR et LALR
3 Utilisation de CAML comme metalangage 
3.1 Description de ocamllex
3.2 Description de ocamlyacc
3.2.1 Analyse d’arbres
3.2.2 Ordre de compilation
3.2.3 Analyse d’expressions arithm´etiques
3.3 D´efinition de c en caml
3.4 D´efinition de java en caml
3.5 D´efinition de caml en caml
4 Typage
4.1 Jugements et r`egles de typage
4.2 Typage d’un langage d’expressions
4.2.1 Premi`ere partie du langage
4.2.2 Deuxi`eme partie du langage
4.2.3 Exemple
4.3 Le typage de c 
4.3.1 Les types de c
4.3.2 R`egles pour le typage de c
4.3.3 Un v´erificateur de types pour c en caml
4.4 R`egles de typage pour java
4.4.1 Notation des types
4.4.2 La relation de sous-classe
5 ´Evaluation 
5.1 ´Evaluation `a l’aide d’environnements
5.1.1 R`egles d’´evaluation pour caml
5.1.2 Un ´evaluateur de caml en caml
5.2 ´Evaluation des traits imp´eratifs 
5.2.1 Regles d’evaluation pour c
5.2.2 Un evaluateur pour c