Majeure 2
Langages et Compilation
Cours 5


Tables des symboles, Frames
Code intermédiaire

jean-jacques.levy@inria.fr

2 mars 1998

Les supports de cours sont en 

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/

Livres:

Introduction

La calculette fonctionnelle

Au cours précédent, l'interpréteur de la calculette posait un léger problème pour la programmation du letrec, où il fallait construire un environnement cyclique. En Caml, on peut construire des données récursives non-fonctionnelles, pourvu qu'un constructeur se trouve entre la définition et les occurences récursives. Ainsi: 

let rec x = 1 :: x in ...
type enregistrement = {hd: int; tl: enregistrement};;
let rec x = {hd = 1; tl = y}  and  y = {hd = 2; tl = x} ;;

sont autorisés.

En http://pauillac.inria.fr/$\sim$levy/x/m2/, on trouve les solutions en Caml et en C. (On peut comparer leur longueur respective).

Sémantique opérationnelle - bigstep SOS

$\begin{array} {cc} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}n = n & {\mbox{$... ...ver \mbox{$ \rho, y=v \mathrel{\raisebox{-.25ex}{$\vdash$}}x = v$}}\end{array}$

Sémantique opérationnelle - bis


$\begin{array} {c} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}\mathop{\mathtt{fun... ...dash$}}\mathop{\mathtt{letrec}}x = e \mathrel{\mathtt{in}}e'= v'$}} \end{array}$

Adaptant la technique de Barendregt(72) pour le $\lambda$-calcul de Church(30), Plotkin(78) a été le promoteur de cette technique de description, aussi appelée sémantique naturelle. Il existe d'autres techniques pour donner un sens aux programmes, notamment la sémantique dénotationnelle de Scott(70) et Strachey(68).

Appel par valeur, appel par nom

On calcule la valeur v d'un paramètre avant de le passer à une fonction

$ \begin{array} {@{\hspace{0ex}}lcl} v & ::= & n \mid (\mathop{\mathtt{fun}}x \rightarrow e)[\rho]\end{array}$

comme en C, Caml, Java, Pascal.

On peut changer la sémantique pour faire une évaluation paresseuse, qui n'évalue pas l'argument avant de le passer à une fonction ou procédure. C'est l'appel-par-nom d'Algol, Miranda, Haskell, LML, Gaml. On change alors la SOS. En paresseux, on fabrique un nouveau type d'expressions qu'on évaluera plus tard: les thunk ou glaçons $e [\rho]$

Sémantique opérationnelle paresseuse- bigstep

$\begin{array} {cc} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}n = n & {\mbox{$... ...ver \mbox{$ \rho, y=v \mathrel{\raisebox{-.25ex}{$\vdash$}}x = v$}}\end{array}$

Sémantique opérationnelle paresseuse - bis

$\;\begin{array} {c} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}\mathop{\mathtt{f... ...dash$}}\mathop{\mathtt{letrec}}x = e \mathrel{\mathtt{in}}e'= v'$}} \end{array}$

En appel paresseux, le résultat est le même si on remplace les arguments dans le corps des fonctions

$(\mathop{\mathtt{fun}}x \rightarrow e) (e') \equiv e\{x := e'\}$

(copy rule). Autrement dit, une expression a le même sens quelle que soit sa place dans le programme (referential transparency). C'est un argument pour la parallélisation automatique.

Portée des noms, bloc d'activations et piles

L'environnement $\rho$ est gérée comme une liste d'association dans l'exemple de la calculette fonctionnelle. Les valeurs des expressions sont des nombres ou des fermetures, ie paires (fonction, environnement). Si on ne retourne jamais de fonctions, on peut se contenter d'une pile pour gérer les environnements, même si on passe des fonctions en arguments, comme en Pascal, Algol, ou Modula.

Cette remarque due à Randell et Russel(60) a permis d'interpréter ces langages avec des piles comme seul espace d'allocation mémoire, et donc de les compiler simplement.

SOS pour blocs d'activations

Modifions la SOS (en appel par valeur) pour faire apparaître la notion de pile pour gérer l'environnement. Les valeurs sont maintenant

$ \begin{array} {@{\hspace{0ex}}lcl} v & ::= & n \mid (\mathop{\mathtt{fun}}x \rightarrow e)[s]\end{array}$

où s est un nombre permettant d'accéder au s-ième élément de l'environnement $\rho$ courant.

Posons
$\vert\rho\vert$ pour la longueur de $\rho$,
$\rho[1..s]$ pour la suite des s premiers éléments de $\rho$.

SOS pour blocs d'activations

$\begin{array} {c@{\hspace{0ex}}c} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}n =... ...box{$ \rho, (s, y=v') \mathrel{\raisebox{-.25ex}{$\vdash$}}x = v$}}\end{array}$

SOS pour blocs d'activations - bis

$\,\begin{array} {c} \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}\mathop{\mathtt{f... ...dash$}}\mathop{\mathtt{letrec}}x = e \mathrel{\mathtt{in}}e'= v'$}} \end{array}$

$\rho$ a le comportement d'une pile, dont le bas se lit à gauche et le sommet à droite.

Blocs d'activations et liaison statique

A chaque appel de fonction (ou pour chaque let, on empile une paire (valeur, lien statique). Nous n'avons considéré que les fonctions unaires. Mais une variation sur la sémantique précédente permet de traiter le cas n-aire. Alors à chaque application de n arguments à une fonction, on créera un n+1-uplet $(s, x_1=v_1, \cdots x_n=v_n)$, ie un bloc d'activation (frame) contenant au moins ce n-uplet. Ce bloc sera libéré quand l'appel de fonction sera terminé et rendra sa valeur.

Tous les langages ne peuvent s'évaluer ainsi. C'est le cas pour notre calculette fonctionnelle (PCF). Par exemple:

$ \rho \mathrel{\raisebox{-.25ex}{$\vdash$}}(\mathop{\mathtt{fun}}x \rightarrow\... ... \rightarrow x)(1) = (\mathop{\mathtt{fun}}y \rightarrow x)[\vert\rho\vert + 1]$ !!

Blocs d'activations et liaison statique - bis

Il faut faire une analyse d'échappements (escape analysis) pour savoir si on peut le faire. (cf Blanchet(98) pour ML)

Tout Pascal marche, car les valeurs fonctionnelles passées uniquement en argument font toujours référence à des environnements plus bas dans la pile. C marche aussi, puisque le lien statique dans C vaut toujours 1, puisqu'on ne peut pas déclarer de fonctions dans des fonctions. On peut donc retourner des fonctions sans problèmes d'allocation de pile.

Blocs d'activations et variables locales

Dans les blocs d'activations, on met aussi les variables locales engendrées par les let. On accède donc à toutes les variables par une indirection et un déplacement par rapport au début du bloc d'activation dont l'adresse est contenue dans le pointeur d'activation (frame pointer). Un autre pointeur intéressant est le pointeur de pile, (stack pointer). L'entrée et la sortie des procédures / fonctions consistera à leur fixer une bonne valeur.

En Pascal, on a vu qu'un programme (manipulant des listes ou arbres) n'a pas toutes ses données allouées dans les différents blocs d'activation de la pile d'exécution. Il y a aussi besoin d'un tas (heap) où on met les données créées dynamiquement (cf plus tard).

Un petit langage impératif à compiler

On utilisera le langage Tigre d'Appel, en Caml-isant la syntaxe. La BNF se trouve en http://pauillac.inria.fr/$\sim$levy/x/m2/ctig/

Voici un exemple de programme en CTigre. 

let N := 100 in
type Tableau = array of int in
let TriInsertion (a:Tableau) = 
    let j := 0 and v := 0 in
        for i := 2 to N do 
            v := a[i]; j := i;
            while a[j-1] > v do
                a[j] := a[j-1]; j:= j-1 
                done;
            a[j] := v
        done in
let a := array [N] of 0 in

a[1] := 3; a[2] := 2; a[3] := 1;
TriInsertion (a)

Un petit langage impératif à compiler - bis

Un autre exemple avec des structures de données dynamiques. 

type ListeInt = {hd: int, tl: ListeInt} in
let TriFusion (x: ListeInt, y: ListeInt) =
    if x = nil then y else
    if y = nil then x else
    if hd(x) <= hd(y) then
        ListeInt{hd = hd(x), TriFusion (tl(x), y)
    else
        ListeInt{hd = hd(y), TriFusion (x, tl(y))
in
let x = ListeInt{hd = 3, tl =  ListeInt{hd = 2, tl = nil}} 
and y = ListeInt{hd = 1, tl =  ListeInt{hd = 4, tl = nil}} 
in TriFusion (x, y)

La BNF de CTigre 

programme ::=  expression 

expression  ::= 
       primary-expression
     | construction-expression
     | nary-expression
     | sequencing-expression

primary-expression  ::=  
       ident
    |  constant
    |  ( expression )
    |  begin expression end

construction-expression  ::= 
    |  type-id [ expression ] of expression
    |  type-id { label = expression {; label = expression } }

nary-expression  ::=  
        ident ( expression {, expression } )
     |  - expression  |  expression bin-op expression
     |  l-value       |  l-value := expression

sequencing-expression  ::=  
        expression ; expression
     |  if expression then expression [  else expression ]
     |  while expression do expression done  |  break
     |  for ident = expression (  to |  downto ) expression do expression done
     |  type  type-binding  { and type-binding }  in expression
     |  let  let-binding  { and let-binding }  in expression

l-value ::= ident  |  l-value.label  |  l-value [ expression ]

type-binding  ::=  id = type-expression

type-expression   ::=  
        type-id
  |  { ty-fields }
  |  array of type-id

let-binding ::=
        ident [: type-id ] := expression 
     |  ident ( ty-fields ) [: type-id ] = expression 

ty-fields  ::=  [  ident : type-id  {, ident : type-id } ]
    
bin-op  ::=  + | -  | * | /  | = | <> | < | <= | > | >= 

constant ::= integer-literal | string-literal | nil

type-id  ::=  ident

label  ::=  ident

Plan pour la suite


CTigre ressemble à Pascal. Il n'a pas de pointeurs. Ses structures de données sont les entiers, chaînes, tableaux et enregistrements, qui peuvent être récursifs (comme en Caml ou Java). Les variables sont toutes modifiables.

Le plan est donc de construire l'AST (arbres de syntaxe abstraite) de CTigre, et d'avoir très rapidement un interpréteur, qui ne sera qu'une légère modification de celui de la calculette PCF.

Puis, on construira un générateur de code pour CTigre, l'optimum étant de pouvoir générer du code machine pour R-2000, dont nous avons l'interpréteur spim, xspim de Larus (Wisconsin 97) sur les machines de l'X. Une autre solution sera de générer du code pour le Pico-Risc de Weis et Leroy (chapitre 13 du livre Le langage Caml).

AST de CTigre

$ \begin{array} {@{\hspace{0ex}}lcl} e, e' & ::= & \mbox{NilExp}\mid \mbox{IntE... ...ots d_{t_n} \\ l_f &::= & (x_1,t_1), (x_2,t_2), \cdots (x_n,t_n) \\ \end{array}$

où x,f, t sont des noms de variables, champs ou type.

Sémantique de CTigre

On ne donne pas la SOS. C'est faisable, en remarquant qu'alors les environnements $\rho$ sont des fonctions des noms dans les locations, et qu'il faut donc manipuler un état mémoire s, fonction des locations dans les valeurs. $\rho(x)$ est aussi appelé left-value de x. Les règles sont de la forme $\rho \mathrel{\raisebox{-.25ex}{$\vdash$}}\langle e, s\rangle = \langle v, s'\rangle$, où s et s' sont les états mémoire de début et de fin d'évaluation. Exercice?!

Qques remarques:

- deux types d'expressions avec résultat ou sans, ce qui fait la différence entre les 2 cas de déclaration de fonctions,

- les chaînes ne servent que pour les fonctions de librairies (impression, concaténation, etc). On peut tester leur égalité.

IC: un langage intermédiaire

La première idéalisation de la machine cible contient 2 types d'objets:

$ \begin{array} {@{\hspace{0ex}}lcl} e, e' & ::= & \mbox{CONST}(n) \mid \mbox{NA... ...x{BINOP}(op, e, e') \mid \mbox{CALL}(e, args) \mid \mbox{ESEQ}(s, e)\end{array}$

$ \begin{array} {@{\hspace{0ex}}lcl} s, s' &::=& \mbox{MOVE}(e, e') \mid \mbox{E... ..., e, e', l_t, l_f) \\ &\mid& \mbox{SEQ}(s, s') \mid \mbox{LABEL}(l)\end{array}$

$ \begin{array} {@{\hspace{0ex}}lcl} args &::=& e_1, e_2, \cdots e_n\\ targets &::=& l_1, l_2, \cdots l_n\end{array}$

IC: un langage intermédiaire - bis

Un programme sera une liste d'association (l, e) ou (l, s). On pourra utilisé les tables avec hachage de Caml pour aller plus vite.

Les noms l sont des étiquettes (comme en assembleur). $\mbox{TEMP}(t)$ est le registre t. On suppose un nombre infini de registres. $\mbox{MEM}(e)$est la mémoire d'adresse e. $\mbox{ESEQ}(s,e)$ donne la valeur de e après avoir fait s.

Dans les instructions, on fait surtout $\mbox{MOVE}(\mbox{TEMP}(t),e)$ et $\mbox{MOVE}(\mbox{MEM}(e), e')$. Dans $\mbox{JUMP}(e,targets)$, la valeur de e doit être incluse dans targets. (C'est pour faciliter les analyses ultérieures). $\mbox{EXP}(e)$ évalue e et oublie sa valeur. $\mbox{SEQ}(s,s')$fait s puis s'. Et $\mbox{LABEL}(l)$ définit l'étiquette l.

IC: un langage intermédiaire - ter


$\mbox{CALL}(e, args)$ appelle la procédure à l'adresse e. $\mbox{CALL}$ calcule son corps en créant un bloc $\mbox{MEM}'(\mbox{TEMP}(fp), nW)$ où figurent les valeurs des n arguments (W est la taille d'un mot mémoire). Le résultat de $\mbox{CALL}$ est la valeur de l'expression, corps de la fonction (valeur folklo si c'est une procédure). $\mbox{CALL}$ a donc une interaction avec le mécanisme d'adressage de toutes les variables, via le registre $\mbox{TEMP}(fp)$.

$\mbox{CALL}$ évalue les arguments args (dans un sens non précisé) et donne la main à la procédure / fonction qui se trouve en e avec les arguments en $\mbox{MEM}(\mbox{TEMP}(fp))$, $\mbox{MEM}(\mbox{TEMP}(fp)+W)$,...$\mbox{MEM}(\mbox{TEMP}(fp)+(n-1)W)$ où W est la taille du mot machine.

Le retour de $\mbox{CALL}$ remet $\mbox{TEMP}(fp)$ à son ancienne valeur.

Syntaxe concrète pour IC

Pour arriver à lire la traduction, on va écrire le code IC sous forme humaine (sans arbres en espérant que la traduction en arbre est évidente).

if e then e1 else e2 devient 

if e then goto l1 else goto l2 {l1,l2}; r; done:
l1: r := e1; goto done {done}
l2: r := e2; goto done {done}

while e do e1 done devient 

loop: if e then goto l1 else goto done {l1,done}
l1: e1; goto loop  {loop}
done: r

Quelques autres traductions


for i := e1 to e2 do body done devient 


let i := e1
and limite := e2
in  while i <= limite do
      body;
      i := i + 1
    done
Les variables simples

La location d'une variable est dans un bloc d'activation. On suppose que le frame pointer est toujours disponible dans le registre $\mbox{TEMP}(fp)$. L'accès à une variable du bloc courant est donc

$\mbox{MEM}(\mbox{BINOP}(+, \mbox{CONST}(k), \mbox{TEMP}(fp)))$ ou encore mem[fp-k]

Si la variable est défini dans un bloc n fois englobant, on suit le lien statique pour arriver à sa valeur

mem[...[mem[mem[fp-k1]-k2]...-kn]]

où $k_1 \cdots k_{n-1}$ sont les adresses des liens statiques dans les blocs et kn est l'adresse de la variable recherchée.

Let et letrec

let x1 = v1 and x2 = v2 and ... xn = vn se traduit par la création d'un nouveau bloc $\mbox{MEM}'(\mbox{TEMP}(fp), (n+1)W)$ contenant les valeurs des variables et le lien statique pour accéder aux variables des blocs englobant. Alors ce lien vaut la valeur de l'ancien fp.

La taille réservée peut être plus grande si des tableaux ou des enregistrements sont déclarés dans let.

letrec a le même comportement.

Calcul du lien statique


Les définitions de procédures peuvent être emboitées, on passe donc aussi à l'appel le lien statique du corps de la procédure appelée. Celui-ci est le lien statique du bloc contenant la définition de la fonction appelée. Donc si la procédure est définie dans un bloc n-fois englobant, on ira chercher ce lien statique comme pour accéder une variable simple.

call(f, e1, e2, ... en, mem[...[mem[mem[fp]]...]+k]])

si on suppose le liens statique toujours rangé au premier mot de chaque bloc. C'est cette valeur qu'on passe en argument supplémentaire.

Données non scalaires


Pour accéder à a[i], on doit faire mem[fp+i*t+a] où t est la taille d'un élément du tableau. On pourra générer un test pour le débordement des bornes du tableau. (Si on est savant, on peut même faire de l'interprétation abstraite des indices, pour ne générer ces tests que s'ils sont utiles. Par exemple, dans la séquence: i:=1; .. a[i] ..., ce n'est pas la peine.

Les accès aux enregistrements ressemblent à ceux des tableaux. Il faut calculer le déplacement correspondant à chaque champ, mem[fp+k_i].

Annexes


3/7/1998