Traduction ? Compilation ?
Principes
Lorsque l’on programme, on préfère généralement utiliser des langages dits de haut niveau. Sous-entendu, de haut niveau d’abstraction, c’est-à-dire un langage qui fournit directement des constructions abstraites compréhensibles (avec plus ou moins de boulot) par un être humain. Ce genre de langages, comme C++, ou Java dans ce cours (mais aussi de nombreux autres) permettent l’utilisation de constructions et concepts riches (les boucles, les objets, la récursion, etc.), mais ne peuvent être compris directement par la machine. C’est pour cela que l’on doit traduire un programme écrit dans un langage de haut niveau vers un langage de bas niveau compréhensible par la machine. Ce processus est appelé compilation, et est automatisé par des programmes appelés compilateurs.
Exemple
En guise d’exemple, considérez le programme suivant qui calcule et affiche le
PGCD de a et b par l’algorithme d’Euclide, écrit en C (dont la classification
en langage de haut niveau est discutable…) :
int main() {
int a = 420;
int b = 126;
while (a != b)
if (a > b)
a = a - b;
else
b = b - a;
printf("%d\n", a);
return 0;
}
Normalement, vous devriez être capable de le lire et de le comprendre, la syntaxe étant très proche de ce que l’on pourrait écrire en Java. Maintenant, voici le résultat de sa compilation par le compilateur libre GCC en langage assembleur (le dernier langage avant le langage machine qui lui, est illisible) :
.LC0:
.string "%d\n"
main:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $420, -4(%rbp)
movl $126, -8(%rbp)
jmp .L2
.L4:
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L3
movl -8(%rbp), %eax
subl %eax, -4(%rbp)
jmp .L2
.L3:
movl -4(%rbp), %eax
subl %eax, -8(%rbp)
.L2:
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jne .L4
movl -4(%rbp), %eax
movl %eax, %esi
movl $.LC0, %edi
movl $0, %eax
call printf
movl $0, %eax
leave
ret
Cette fois, il devrait être plus difficile pour vous de comprendre ce programme. On comprend pourquoi l’on veut que la compilation soit automatisée.
Dans ce cours
Le but de ce cours est de vous introduire à ce processus de compilation. Pour ce faire, vous allez endosser le rôle du compilateur et traduire vous-mêmes des programmes. Pour vous faciliter la vie, vous n’allez pas apprendre un langage bas niveau comme l’assembleur. Vous allez plutôt traduire des programmes Java vers un sous-ensemble cible de Java, dans une forme particulière, proche de ce que pourrait produire un compilateur.
Le sous-ensemble cible
Squelette général des programmes
Les programmes traduits que l’on veut écrire ont tous la même forme, suivant un modèle d’exécution simple. Le programme consiste en une séquence d’instructions indexées par des entiers, exécutées l’une apres l’autre dans une boucle infinie. L’index de l’instruction à exécuter à chaque tour est maintenu dans une variable, le compteur d’instructions. Les instructions peuvent agir sur une représentation de la mémoire en tableau. On peut néanmoins continuer d’utiliser des variables pour représenter les données, en particulier si l’on manipule plusieurs types. Voici le squelette général d’un programme traduit :
class ProgTrad {
public static void main(String[] args) {
// Déclaration du compteur d'instruction et de la mémoire
int ic = 0;
int[] mem = new int[100000];
// Boucle d'exécution
while (true) {
switch (ic++) {
// Liste des instructions
case 0: ... break;
case 1: ... break;
...
}
}
}
}
Sous-ensemble des instructions
Le tableau ci-dessous répertorie les instructions que l’on s’autorise :
| Instruction | Description |
|---|---|
mem[e1] = e2; |
Affectation, où e1 et e2 sont des expressions simples |
ic = e; |
Saut, par modification du compteur d’instructions pour le prochain tour |
if (test) ic = e; |
Saut conditionnel |
System.exit(0); |
Fin du programme |
On s’autorise également les modifications relatives du type ++, +=, *=,
etc., ainsi que les appels aux fonctions d’entrée / sortie comme System.out.println().
Méthodologie
Rappelez-vous que la compilation est un processus systématique, automatique.
En cela, la traduction s’apparente à suivre une recette de cuisine (une recette
un peu compliquée).
Il vous faut simplement faire attention aux structures qui ne sont plus
disponibles, c’est-à-dire le branchement if / else et les boucles for
et while.
Reprenons notre exemple d’algorithme d’Euclide en Java cette fois :
class Euclide {
public static void main(String[] args) {
int a = 420;
int b = 126;
while (a != b)
if (a > b)
a = a - b;
else
b = b - a;
System.out.println(a);
}
}
La première étape est d’identifier les variables, ici les entiers a et b, et
de leur attribuer une adresse fixe dans la mémoire.
Ici on peut décider que a aura l’index 0 et b l’index 1
dans la mémoire vue comme un tableau d’entiers, c’est arbitraire, le tout est de
rester cohérent.
int x = 42; se cachent 2 choses : une déclaration,
c’est-à-dire la réservation d’un espace mémoire attribué à la variable x
suffisamment grand pour contenir un entier, et une affectation de la valeur 42
à la variable.
Les 2 déclarations de notre programmes vont donc être traduites en 2 instructions dans notre programme traduit, dont voici la base :
class EuclideTrad {
public static void main(String[] args) {
int ic = 0;
int[] mem = new int[100000];
while (true) {
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
...
}
}
}
}
Vient ensuite la boucle while.
Pour commencer, l’idée est de tester la condition de boucle : si le test
réussit, on va exécuter le code de la boucle qui vient directement après, sinon
on saute ce code pour parvenir directement, au tour d’après, à l’instruction qui
suit la boucle.
Dans notre sous-ensemble cible, on dispose d’une seule instruction permettant de
tester : le saut conditionnel.
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
// test de boucle : si le test échoue on saute le corps de la boucle
case 2: if (mem[0] == mem[1]) ic = ?; break; // <index de l'instruction après le while>
...
Pour l’instant, on ne connaît pas encore forcément l’index de l’instruction
après la boucle (on peut, mais avançons petit-à-petit).
L’instruction du corps de boucle est un branchement.
On va procéder comme pour une boucle en testant la condition : si le test
réussit, on poursuit avec le code du if, sinon on saute ce code pour aller
exécuter le code du else.
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
// test de boucle : si le test échoue on saute le corps de la boucle
case 2: if (mem[0] == mem[1]) ic = ?; break; // <index de l'instruction après le while>
// branchement
case 3: if (mem[0] <= mem[1]) ic = ?; break; // <index de la 1ère instruction du else>
case 4: mem[0] = mem[0] - mem[1]; break; // code du if
...
if, on ne veut pas enchaîner avec l’exécution
du code du else !
Il faut donc sauter le code du else, pour arriver à l’instruction qui suit le branchement.
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
// test de boucle : si le test échoue on saute le corps de la boucle
case 2: if (mem[0] == mem[1]) ic = ?; break; // <index de l'instruction après le while>
// branchement
case 3: if (mem[0] <= mem[1]) ic = ?; break; // <index de la 1ère instruction du else>
case 4: mem[0] = mem[0] - mem[1]; break; // code du if
case 5: ic = ?; break; // saut à l'<index de l'instruction après le branchement>
case 6: mem[1] = mem[1] - mem[0]; break; // code du else
...
La prochaine instruction va permettre d’implémenter le comportement de boucle : il faut revenir à l’instruction à laquelle la condition de boucle est testée. De plus, on a maintenant toutes les infos suffisantes pour indiquer les sauts sans se tromper :
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
// test de boucle : si le test échoue on saute le corps de la boucle
case 2: if (mem[0] == mem[1]) ic = 8; break; // <index de l'instruction après le while>
// branchement
case 3: if (mem[0] <= mem[1]) ic = 6; break; // <index de la 1ère instruction du else>
case 4: mem[0] = mem[0] - mem[1]; break; // code du if
case 5: ic = 7; break; // saut à l'<index de l'instruction après le branchement>
case 6: mem[1] = mem[1] - mem[0]; break; // code du else
case 7: ic = 2; break; // retour au test de la boucle
...
On termine avec l’affichage et la sortie du programme:
class EuclideTrad {
public static void main(String[] args) {
int ic = 0;
int[] mem = new int[100000];
while (true) {
switch (ic++) {
// initialisations
case 0: mem[0] = 420; break;
case 1: mem[1] = 126; break;
// test de boucle : si le test échoue on saute le corps de la boucle
case 2: if (mem[0] == mem[1]) ic = 8; break; // <index de l'instruction après le while>
// branchement
case 3: if (mem[0] <= mem[1]) ic = 6; break; // <index de la 1ère instruction du else>
case 4: mem[0] = mem[0] - mem[1]; break; // code du if
case 5: ic = 7; break; // saut à l'<index de l'instruction après le branchement>
case 6: mem[1] = mem[1] - mem[0]; break; // code du else
case 7: ic = 2; break; // retour au test de la boucle
case 8: System.out.println(mem[0]); break; // affichage
case 9: System.exit(0); // sortie
}
}
}
}
while.
La traduction d’une boucle for suit sensiblement les mêmes principes mais est
un peu plus complexe car elle embarque 2 instructions en plus du test :
l’initialisation (par exemple int i = 0), et l’instruction d’itération (par
exemple i++), qu’il faut prendre en compte.
Cette méthodologie devrait vous permettre de parvenir à bout de la feuille de TD 3 .
Appels de fonctions et pile
Principes
Vous êtes maintenant familier avec la notion de fonction. Comme les boucles et les branchements, c’est une abstraction de haut niveau que la machine ne comprend pas directement. Il nous faut un moyen de traduire ce concept. Globalement, tout comme pour les boucles et les branchements, nous allons utiliser des sauts : un appel de fonction est un saut vers une liste d’instructions ailleurs dans le programme, suivi du retour, un saut à l’instruction après l’appel.
Or, nous ne disposons que d’un seul compteur d’instructions, il faut donc, au
moment du saut d’appel, se rappeler de sa valeur au moment de l’appel.
De plus, il faut garder en tête que les fonctions peuvent être arbitrairement
imbriquées : une fonction f peut appeler une fonction g, qui appelle h, et
ainsi de suite.
On ne peut donc pas se permettre de stocker la valeur du compteur d’instructions
dans une variable fixe, au risque de l’écraser à chaque appel imbriqué.
Nous n’avons pas vu les structures de pile pour rien : nous allons utiliser une
pile d’appels pour stocker les valeurs successives du compteur d’instructions.
Le principe pour un appel de fonction est simple :
- on empile l’index de l’instruction qui suit l’appel,
- on effectue le saut vers les instructions de la fonction,
- on exécute les instructions de la fonction (avec éventuellement d’autres appels de fonctions),
- on dépile la valeur en haut de la pile d’appel,
- on saute à l’instruction correspondante, c’est le retour.
Mise à jour du sous-ensemble cible
Pour le moment, on va ignorer la gestion des arguments des fonctions et des
valeurs de retour, nous n’allons donc travailler qu’avec des fonctions void
sans arguments.
On utilise ainsi une simple pile d’entiers pour implémenter la pile d’appels.
Voici donc le nouveau squelette des programmes traduits :
import java.util.Stack;
class ProgTrad {
public static void main(String[] args) {
// Déclaration du compteur d'instruction et de la mémoire
int ic = 0;
int[] mem = new int[100000];
// Déclaration de la pile d'appels
Stack<Integer> p = new Stack<>();
// Boucle d'exécution
while (true) {
switch (ic++) {
// Liste des instructions
case 0: ... break;
case 1: ... break;
...
}
}
}
}
On s’autorise les instructions suivantes pour manipuler la pile :
| Instruction | Description |
|---|---|
p.push(ic); ic = e; |
Appel de fonction : on empile l’index de la prochane instruction et on saute à l’instruction numéro e (étapes 1. et 2.) |
ic = p.pop(); |
Retour de fonction : on dépile l’index de l’instruction suivant l’appel et on y saute (étapes 4. et 5.) |
Exemple et méthodologie
Adaptons un des exemples le plus connu de récursion mutuelle : le but est de déterminer la parité d’un entier. Une manière de faire est de procéder récursivement avec deux fonctions qui s’appellent mutuellement :
class Parite {
static int n;
static void estPair() {
if (n == 0)
System.out.println("oui");
else {
n--;
estImpair();
}
}
static void estImpair() {
if (n == 0)
System.out.println("non");
else {
n--;
estPair();
}
}
public static void main(String[] args) {
n = 42;
estPair();
}
}
Il faut simplement adapter notre méthodologie pour gérer les appels.
Tout d’abord on va traduire les instructions de la fonction main :
import java.util.Stack;
class PariteTrad {
public static void main(String[] args) {
int ic = 0;
int[] mem = new int[100000];
Stack<Integer> p = new Stack<>();
while (true) {
switch (ic++) {
// initialisation
case 000: mem[0] = 42; break;
// appel à estPair
case 001: p.push(ic); ic = ?; break; // <index de la 1ère instruction de estPair>
case 002: System.exit(0); // fin du programme
...
}
}
}
}
Quel index choisir pour la 1ère instruction de estPair() ?
On peut faire un choix complètement arbitraire, en faisant simplement attention
à ce que nos blocs d’instructions ne se recouvrent pas.
L’index 100 par exemple, est très bien, et on peut procéder à la traduction de
estPair() :
switch (ic++) {
// initialisation
case 000: mem[0] = 42; break;
// appel à estPair
case 001: p.push(ic); ic = 100; break; // <index de la 1ère instruction de estPair>
case 002: System.exit(0); break; // fin du programme
// estPair()
case 100: if (mem[0] != 0) ic = 103; break;
case 101: System.out.println("oui"); break;
case 102: ic = 105; break;
case 103: mem[0]--; break;
case 104: p.push(ic); ic = ?; break; // appel à estImpair
case 105: ic = p.pop(); break; // retour
...
}
Pour l’appel à estImpair(), on procède exactement de la même façon, et on peut
choisir l’index 200 pour sa 1ère instruction par exemple :
import java.util.Stack;
class PariteTrad {
public static void main(String[] args) {
int ic = 0;
int[] mem = new int[100000];
Stack<Integer> p = new Stack<>();
while (true) {
switch (ic++) {
// initialisation
case 000: mem[0] = 42; break;
// appel à estPair
case 001: p.push(ic); ic = 100; break; // <index de la 1ère instruction de estPair>
case 002: System.exit(0); break; // fin du programme
// estPair()
case 100: if (mem[0] != 0) ic = 103; break;
case 101: System.out.println("oui"); break;
case 102: ic = 105; break;
case 103: mem[0]--; break;
case 104: p.push(ic); ic = 200; break; // appel à estImpair
case 105: ic = p.pop(); break; // retour
// estImpair()
case 200: if (mem[0] != 0) ic = 203; break;
case 201: System.out.println("non"); break;
case 202: ic = 205; break;
case 203: mem[0]--; break;
case 204: p.push(ic); ic = 100; break; // appel à estPair
case 205: ic = p.pop(); break; // retour
}
}
}
}
Appliquez cette méthodologie aux execrcices de la feuille de TD 4 .