Sommaire

  1. Traductions de base
  2. Traductions des appels de fonctions

Traductions de base

Où l'on traduit des boucles, des conditionnelles, mais pas d'appels de fonctions.

Rappels de cours

L'objectif de cette partie du cours est de comprendre le rôle que joue un compilateur. Un compilateur prend en entrée un programme dans un langage de haut niveau, par exemple Java, et le transforme en un programme dans un langage de bas niveau, typiquement de l'assembleur, qui a le même comportement que le programme de haut niveau.

L'aspect de cette transformation qui nous intéresse dans cette partie est la manière dont le flot de contrôle du programme est traduit. Concrètement, les programmes Java contiennent des conditionnelles if-else et des boucles for et while, alors que l'assembleur utilise d'autres constructions pour contrôler le flot de contrôler les sauts non conditionnels et les sauts conditionnels.

Forme générale d'un programme assembleur

Un programme en assembleur est composé d'une liste d'instructions, et chaque instruction possède une adresse. Dans ce document, on suppose que son adresse est son numéro de ligne.

Au lieu de variables comme en Java, l'assembleur utilise des registres, qui contiennent chacun un entier (en gros, ce sont des variables de type int). Chaque architecture de processeur comporte un certain nombre de registres. Par exemple, ARMv8 contient 31 registres X0,...,X30 pouvant chacun contenir 64 bits.

Un exemple de programme est :

ldr X4, X6   // copie le contenu de X6 dans X4 (load register)
b 1          // saute (branch) de 2 lignes
cmp X4, X7   // compare les contenus de X4 et de X7
b.eq -4      // saute de -3 instructions si la dernière comparaison était égale

L'adresse de la prochaine instruction à exécuter est contenue dans un registre spécial, le compteur d'instructions, ou ic.

Dans ce cours, on simule un tel programme assembleur en un programme Java ayant un forme très particulière. Pour cet exemple, il ressemblerait à :

int ic=0;

while (true) {
    switch (ic++) {
        case 0: mem[4]=mem[6]; break;
        case 1: ic+=1; break;
        case 2: if (mem[4] == mem[7]) ic-=3; break;
    }
}

Notez que les deux dernières instructions du programme assembleur (test + saut) correspondent à une seule ligne dans la version en Java.

Sauts non-conditionnels

Quand on exécute un saut conditionnel b offset, la prochaine instruction à être exécutée est l'instruction à l'adresse courante à laquelle on a ajouté offset. Ce qui correspond dans la version Java à ic += offset.

Sauts conditionnels

En assembleur, les sauts conditionnels se font de deux étapes:

  1. Une instruction de comparaison, par exemple cmp qui enregistre le résultat dans un registre spécial.
  2. Une instruction de saut conditionnelle qui saute si ce registre a une certaine valeur. Par exemple b.eq pour sauter si la dernière comparaison était entre des opérandes qui étaient égales, ou b.gt qui saute si le résultat de la dernière comparaison était "plus grand que".

Dans la version java, on combine ces deux instructions en une seule ligne:

case X: if (condition) ic += offset' break'

Remarque : pour ceux que ça amuse, le site godbolt.org est très bien pour explorer comment les compilateurs traduisent les programmes.

Structure générale des programmes traduits

L'idée est de traduire un programme tel que celui-ci :

class Prog {
    public static void main(String[] a) {
        int k = 0;
        for (int i = 0; i < 6; i++) {
            k += i;
        }
    }
}

en un programme de la forme

class ProgTrad {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: mem[0]=0; break;
                case 1: mem[1]=0; break;
                case 2: if (mem[0]>=6) ic+=3; break;
                case 3: mem[1]+=mem[0]; break;
                case 4: mem[0]++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

Post-incrémentation

Il est important de bien comprendre la ligne

switch (ic++) {

et en particulier le fonctionnement de la post-incrémentation ic++, qui est assez surprenant: qu'affiche le programme suivant?

int x = 4;
if (x++ == 4) {
    System.out.println("Branche gauche, et x vaut" + x);
} else {
    System.out.println("Branche droite, et x vaut" + x);
}

La réponse est Branche gauche, et x vaut 5. La raison est la suivante : la valeur de l'expression x++ est l'ancienne valeur de x, mais le fait d'évaluer cette expression ajoute 1 à x.

Moralement, c'est comme si tous les x++ étaient remplacés par incr(x), un appel à la fonction Java suivante :

public static int incr(int i) {
    int old = i;
    i = i + 1;
    return old
}

sauf qu'en Java les entiers sont passés par valeur, et donc cette fonction ne modifie pas la valeur de x (s'en convaincre).

Pour revenir à nos traductions, cela signifie que si un branche case X ne modifie pas ic, la valeur de ic devient X+1. En somme, l'exemple en haut est équivalent à :

class ProgTrad {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic) {
                case 0: ic += 1; mem[0]=0; break;
                case 1: ic += 1; mem[1]=0; break;
                case 2: ic += 1; if (mem[0]>=6) ic+=3; break;
                case 3: ic += 1; mem[1]+=mem[0]; break;
                case 4: ic += 1; mem[0]++; break;
                case 5: ic += 1; ic-=4; break;
                case 6: ic += 1; System.exit(0);
            }
        }
    }
}

Après que le choix de quelle branche choisir est fait, et avant tout autre chose, on ajoute 1 à ic.

Comment traduire un programme Java

Puisque le but de ce cours est de mieux comprendre ce que fait un compilateur, il nous faut être méthodique. En particulier, on veut que la traduction soit modulaire : chaque construction du programme est traduite sans se soucier du reste du programme. Par exemple, considérons le programme suivant :

class Prog{
    static int i;
    static int k;
    public static void main(String[] a){
        int cpt = 0;
        int k = 10;
        while(k != 1){
            if (k % 2 == 0) { 
                k = k/2;
            } else {
                else k = 3*k+1;
            }
            cpt++;
        }
    }
}

Dans cet exemple, les constructions principales sont : la boucle while et la conditionnelle if. Commençons par la boucle while.

Traduire les boucles while

Une boucle while a cette forme :

while (condition) {
    corps de la boucle;
}

Le flot d'exécution est :

  1. On exécute la condition, ce qui nous donne un booléen.
    • Si ce booléen est vrai, on exécute l'instruction suivante.
    • S'il est faux, on saute la boucle.
  2. On exécute le corps de la boucle.
  3. On recommence à l'étape 1.

On reconnais que l'étape 3 est un saut non conditionnel vers l'instruction qui correspond à 1 ; et l'étape 1 est un saut conditionnel si la condition est fausse. Ainsi la traduction est la suivante:

case X: if (!condition) ic += (Y-X); break;
case X+1: [[ traduction du corps de la boucle ]]
case X+2: [[ ................................ ]]
case X+3: [[ ................................ ]]
case ...: [[ ................................ ]]
case Y: ic -= (Y-X)+1; break;
case Y+1: [[ traduction de la suite du programme ]]

Exercice : comment traduire une boucle do {...} while (cond); ? (C'est comme un boucle while sauf que le corps de la boucle est exécuté au moins une fois)

Traduire une boucle for

Ce cas est similaire au cas des boucles while, avec quelques ajouts. Une boucle for est de la forme :

for (initialisation; condition; incrément) {
    corps de la boucle;
}

Souvent les boucles for sont utilisées pour itérer de 0 jusqu'à N-1:

for (int i = 0; i < N; i++) {
    corps de la boucle;
}

De la même manière que pour les boucles while, on écrit le flot d'exécution d'une boucle for:

  1. On exécute initialisation.
  2. On exécute la condition, ce qui nous donne un booléen.
    • Si ce booléen est vrai, on exécute l'instruction suivante.
    • S'il est faux, on saute la boucle.
  3. On exécute le corps de la boucle.
  4. On exécute incrément.
  5. On recommence à l'étape 2.

Il s'agit du même flot que pour une boucle while en ajoutant une étape d'initialisation au début et une étape d'incrémentation à la fin de la boucle. La traduction est donc de la forme :

case X  : intialisation
case X+1: if (!condition) ic += (Y-X)+1; break; // saute vers Y+2
case X+2: [[ traduction du corps de la boucle ]]
case X+3: [[ ................................ ]]
case X+4: [[ ................................ ]]
case ...: [[ ................................ ]]
case Y  : incrémentation
case Y+1: ic -= (Y-X)+1; break;
case Y+2: [[ traduction de la suite du programme ]]

Traduire une conditionnelle

On considère une conditionnelle

if (condition) {
    branche_then;
} else {
    branche_else;
}

Le flot de considère est le suivant:

  1. On exécute la condition.
    • Si elle est vraie:
      • on exécute branche_then,
      • on saute vers la première instruction après la conditionnelle.
    • Si elle est fausse:
      • on saute vers branche_else,

Ainsi, on ne fait un saut conditionnel que lorsque la condition est fausse. La traduction est donc:

case X: if (!cond) ic += ...; // on saute vers Y+1
case X+1: [[ traduction de branche_then ]]
case X+2: [[ .......................... ]]
case X+3: [[ .......................... ]]
case X+4: [[ .......................... ]]
case ...: [[ .......................... ]]
case Y: ic +=  ...; // on saute vers Z
case Y+1: [[ traduction de branche_else ]]
case Y+2: [[ .......................... ]]
case Y+3: [[ .......................... ]]
case Y+4: [[ .......................... ]]
case ...: [[ .......................... ]]
case Z : [[ traduction de la suite du programme ]]

Concrètement, si la condition est vraie, on ne saute pas, donc on exécute X+1, ensuite le code de la branche fait ce qu'elle veut, et quand elle a terminée on exécute Y qui nous fait sauter au dessus de la branche else jusqu'à la suite du code.

Si la condition est fausse, on commence par sauter au dessus de la branche then et on commence à exécuter la branche else, puis la suite du programme.

Exercice : Comment traduire if (cond1) {...} else if (cond2) {...} else {...} ?

Gestion de la mémoire

Dans la traduction, on ne veut utiliser qu'un unique tableau d'entiers, qu'on va appeler ici mem.

Chaque variable statique sera associée à une certaine case de ce tableau. La difficulté apparait quand une variable statique est elle-même un tableau d'entiers.

Imaginons que nous devons traduire un programme avec les variables statiques suivantes :

static int x;
static int y;
static int[] t1 = new int[58];
static int[] t2 = new int[30];

(On connaitra toujours la taille de ces tableaux à l'avance.) Il s'agit donc de ranger toutes ces variables dans le tableau mem. Une possibilité est:

0   1   2                 60            90
+---+---+-----------------+-------------+
| x | y |    ...t1...     |  ...t2...   |
+---+---+-----------------+-------------+

Ainsi, la valeur de x est dans mem[0], et a valeur de la j-ème case de t2 est dans mem[60 + j], puisque le tableau t1 commence à la case 60 de mem.

Pour traduire t2[x], on utilisera alors mem[60 + mem[0]]. Notez que la valeur de x dans le programme d'origine reste la même que la valeur de mem[0] dans le programme traduit.

Corrections d'exercices du TD3

Voici la correction des deux premiers exercices du TD 3.

Exercice 1 : traduction inversée

Le programme que cet exercice considère est le suivant :

class ProgTrad {
    static int i;
    static int k;

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: i=0; break;
                case 1: k=0; break;
                case 2: if (i>=6) ic+=3; break;
                case 3: k+=i; break;
                case 4: i++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

On rappelle que la post-incrémentation de la variable ic dans le switch(ic++) ajoute 1 à la variable ic après que le choix de quelle branche prendre est fait. Ainsi, par exemple, quand on est dans la branche case 3: la variable ic vaut 4. Voir ici.

  1. Exécuter ce programme en notant l'évolution du contenu des variables.
Étapeikcommentaire
0??
10?
200
300on ajoute i = 0 à k
410
511on ajoute i = 1 à k
621
723on ajoute i = 2 à k
833
936on ajoute i = 3 à k
1046
11510on ajoute i = 4 à k
12510
13515on ajoute i = 5 à k
14615le test i >= 6 est vrai donc on s'arrête
  1. Préciser ce que calcule ce programme

Déjà, on remarque une structure de boucle, avec un saut conditionnel en case 2 et un saut non conditionnel en case 5 vers le saut conditionnel.

On voit que le programme ajoute la valeur courante de i à k à chaque tour de boucle, et que i est incrémenté de 1 à chaque fois. De plus, on commence avec i contenant 0, et on s'arrête dès que i est supérieur ou égal à 6.

Ainsi, le programme calcule 0+1+2+3+4+5 = 15.

  1. Fort de notre analyse du programme, il est naturel d'utiliser une boucle for comme suit. Si l'on veut coller exactement avec ProgTrad au dessus, notamment au niveau de l'ordre où sont initialisées les variables, on peut faire :
class Prog {
    static int i;
    static int j;

    public static void main(String[] a) {
        i = 0;
        k = 0;
        for (; i < 6; i++) {
            k += i;
        }
    }
}

Bien sûr, le code java plus idiomatique est le suivant :

class Prog {
    public static void main(String[] a) {
        int k = 0;
        for (int i = 0; i < 6; i++) {
            k += i;
        }
    }
}
  1. Écrire une variante de ProgTrad qui remplace l'utilisation des variables i et j par des accès à un unique tableau d'entiers mem.

Il s'agit simplement de représenter chaque variable par une case de tableau mem. La convention que j'utilise ici est que i correspond à la case 0, et k à la case 1. Pratiquement, on remplace chaque occurrence de i par mem[0] et chaque occurrence de k par mem[1].

class Prog {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: mem[0]=0; break;
                case 1: mem[1]=0; break;
                case 2: if (mem[0]>=6) ic+=3; break;
                case 3: mem[1]+=mem[0]; break;
                case 4: mem[0]++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

Exercice 2 : factorielle

On rappelle que \( n! = 1 \times 2 \times \ldots \times (n-1) \times n \), en convenant que \( 0! = 1 \).

  1. Écrire un programme qui calcule la factorielle d'un nombre (ici, 11).

Pour la calculer itérativement, on utilise un accumulateur k qui commencera égal à 1, et qu'on multiplie par 1, puis par 2, puis par 3... dans une boucle.

class Factorielle {
    public static void main(String[] a) {
        int k = 1;
        for (int i = 1; i < 12; i++) {
            k *= i;
        }
        // ici, k contient la factorielle de 11
    }
}
  1. Traduire le programme Factorielle sur le modèle de Prog

On utilise une variable statique de classe pour chaque variable (ici: i et k) et on traduit la boucle comme dans le cas de ProgTrad par la structure:

    case X: // saut conditionnel vers Y+1 si la condition de la boucle est fausse
    ...
    ...
    case Y: // saut inconditionnel vers X à la fin de la boucle
    case Y+1: // première instruction après la boucle

Dans notre cas, cela donne :

class FactorielleTrad {
    static int i;
    static int k;

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: i = 1; break;
                case 1: k = 1; break;
                case 2: if (i >= 12) ic += 3; break;
                case 3: k *= i; break;
                case 4: i++; break;
                case 5: ic -= 4; break;
                case 6: System.exit(0);
            }
        }
    }
}

En résumé, on a remplacé k += i par k *= i et on a changé les valeurs initiales des variables.

Exercice 3 : suite de Syracuse

La suite de Syracuse de l'entier \( n \) est définie par: \( u_0 = n\), et pour tout entier \(k\), si \( u_k \) est pair alors \( u_{k+1} = u_k/2 \) et sinon \( u_{k+1} = 3 u_k + 1 \). On veut savoir au bout de combien d'étapes on tombe sur 1.

  1. Ce programme Java calcule cette valeur :
public class Syracuse {
    public static void main(String[] a) {
        int u = 13; // on prend n = 13
        int vol = 0; // le temps de vol
        while (u != 1) {
            if (u % 2 == 0) {
                u = u/2;
            } else {
                u = 3 * u + 1;
            }
            vol += 1;
        }
        System.out.println("Le temps de vol de 13 est " + vol + "!");
    }
}
  1. On suit la méthode détaillée dans dans les rappels de cours. On décide que u correspond à mem[0] et que vol correspond à mem[1].

On commence par l'initialisation de u et l'impression du message. (On omet les break à chaque ligne du switch)

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
              // TODO: traduire la boucle while
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

Ensuite on traduit la boucle while avec un saut conditionnel au début et un saut inconditionnel à la fin.

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += ?; // saut vers Z
            // traduction du if et de vol += 1
            case Z-1: ic -= ?; // saut vers 1
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

Pour finir, on traduit le contenu de la boucle:

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += ?; // saut vers Z
            case 2: if (mem[0] % 2 != 0) ic += 2; // saut vers 5
            case 3: mem[0] = mem[0] / 2;
            case 4: ic += ?; // saut vers Z-1 (fin de la boucle)
            case 5: mem[0] = 3 * mem[0] + 1;
            case Z-1: ic -= ?; // saut vers 1
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

On peut finalement remplacer Z par la bonne valeur pour que les adresses des instructions soient continues, et donc on peut remplir les décalages des sauts.

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += 6; // saut vers la fin
            case 2: if (mem[0] % 2 != 0) ic += 2; // saut vers else
            case 3: mem[0] = mem[0] / 2;
            case 4: ic += 1; // saut vers la fin de la boucle
            case 5: mem[0] = 3 * mem[0] + 1;
            case 6: ic -= 6; // saut vers 1
            case 7: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case 8: System.exit(0);
            }
        }
    }
}

Exercice 4 : Partiel 2011

Il s'agit de traduire le programme suivant :

class Partiel2011 {
    static int[] t;
    static int i;

    public static void main(String[] args) {
        t = new int[20];
        t[0] = 1;
        t[1] = 1;
        for (i = 2; i < 20; i++) {
            t[i] = 2 * t[i-1] + t[i-2];
        }
        System.out.println("Nombre(19) = " + t[19]);
    }
}

On décide que i sera dans la case 0 de mem, et la tableau t dans les cases 1 jusqu'à 20 de mem.

Ensuite on traduit le programme sauf la boucle for:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
               // traduction de la boucle 
            case Z: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case Z+1: System.exit(0);
            }
        }
    }
}

Il suffit maintenant de traduire la boucle for:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
            case 2: mem[0] = 2; // initialistion
            case 3: if (i >= 20) ic += ??; // saut vers Z
            case 4: mem[1+mem[0]] = 2 * mem[1+ mem[0]-1] + mem[1 + mem[0]-2];
            case Z-2: mem[0]++;
            case Z-1: ic -= ??; // saut vers 3;
            case Z: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case Z+1: System.exit(0);
            }
        }
    }
}

Et enfin on peut remplacer Z par 7:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
            case 2: mem[0] = 2; // initialistion
            case 3: if (i >= 20) ic += 3; // saut vers 7
            case 4: mem[1+mem[0]] = 2 * mem[1+ mem[0]-1] + mem[1 + mem[0]-2];
            case 5: mem[0]++;
            case 6: ic -= 4; // saut vers 3;
            case 7: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case 8: System.exit(0);
            }
        }
    }
}

Indications sur les exercices

Des indications sur les exercices 3 et 4 du TD 3.

Exercice 3 : Suite de Syracuse

Question 1.

Il s'agit d'écrire un programme qui calcule la suite de Syracuse d'un entier \((n\)) donné tant que1 l'on m'a pas atteint la valeur 1.

Ainsi, on initialise une variable u à \(n\), puis itérativement on met à jour sa valeur pour qu'elle contienne successivement \(u_0, u_1, u_2, \ldots \). On sort de la boucle quand u vaut 1.

Question 2.

C'est comme les deux premiers exercices du TD, sauf :

  • À l'intérieur de la boucle, il faudra un saut conditionnel car la définition du prochain terme de la suite de Syracuse a deux cas, et donc il y aura un if dans la boucle à traduire.

  • Il s'agit de traduire une boucle while au lieu d'une boucle for, mais le principe est le même car

    while (Cond) { ... }
    

    est la même chose que

    for ( ; Cond; ) { ... }
    

Exercice 4 : Partiel 2011

Il y a deux possibilités.

  • Si on ne veut utiliser qu'un seul tableau mem dans la traduction, en s'interdisant d'avoir autant de variables dans la traduction que dans le programme source, alors il faut fixer une convention pour faire cohabiter i et t. Par exemple, dire que i correspond à mem[0] et que la case j de t correspond à mem[1+j].

  • Sinon, on peut simplement avoir deux variables statiques de classe i et t. Notez que dans la suite du cours on s'interdira de faire cela.

  • 1

    On remarquera que tant que se traduit par while en anglais.

Traductions des appels de fonctions

Où l'on traduit des appels de fonctions et où on utilise les piles

Rappels de cours

Appels de fonctions et pile d'exécution

Considérons un programme Java contenant plusieurs fonctions.

public class Prog {
    public static void f() {
/*F1*/  System.out.println("Dans la fonction f");
    }

    public static void g() {
/*G1*/  System.out.println("Dans la fonction g");
/*G2*/  f();
/*G3*/  System.out.println("Fin de la fonction g");
    }

    public static void main(String[] a) {
/*M1*/  f();
/*M2*/  g();
    }
}

L'exécution de ce programme commence par la fonction main, qui appelle f puis g. La sortie de ce programme est :

Dans la fonction f
Dans la fonction g
Dans la fonction f
Fin de la fonction g

Lors d'un appel de fonction, par exemple l'appel à f à la ligne M1 de la fonction main, le flot d'exécution du programme saute de la ligne M1 jusqu'à la première ligne de la fonction appelée, dans cet exemple, la ligne F1.

Il n'est donc pas surprenant que pour traduire un appel de fonction on utilise un saut non-conditionnel, de la forme ic = XXX.

L'aspect le plus subtil est ce qui se passe lorsque l'exécution arrive à la fin d'une fonction. Dans l'exemple de l'appel à f dans main, une fois la ligne F1 exécutée, on veut que le flot d'exécution reparte de la ligne M2 dans la fonction main.

On pourrait naïvement ajouter à la fin de la traduction de la fonction f un saut non conditionnel vers la ligne M2. Cette idée ne fonctionne pas car la fonction f peut être appelée à plusieurs endroits différents : dans le programme ci-dessus, f est aussi appelée à la ligne G1 dans la fonction g. Et quand elle est appelée depuis g, il faut que f effectue un saut vers G3. Ainsi, la destination du saut à la fin d'une fonction dépend d'où elle a été appelée !

La solution est d'écrire où l'adresse de retour de l'un appel de fonction quelque part juste avant d'effectuer le saut inconditionnel vers le début de son code.

La dernière question est : où écrit-on cette adresse de retour ? Idéalement, une fois la fin de la fonction atteinte, on voudrait que la fonction sache directement où lire cette adresse. La solution est que l'adresse de retour est toujours au sommet de la pile d'exécution du programme.

En résumé :

  • quand on appelle un fonction f
    1. on empile d'adresse de retour (en général la ligne suivante) dans la pile d'exécution,
    2. on saute vers l'adresse de la fonction f.
  • quand on arrive à la fin d'une fonction
    1. on dépile la pile d'exécution, ce qui nous donne l'adresse de retour qui était à son sommet,
    2. on saute vers celle-ci.

Traduction en Java

Dans ce cours, l'ajout de la pile d'exécution revient à ajouter une variable statique dans la traduction

static Stack<Integer> stack = new Stack<>();

On rappelle qu'on utilise

stack.push(44);

pour empiler un nombre, et

int ret = stack.pop();

pour dépiler l'élément qui est au sommet de la pile.

Voici la traduction du programme ci-dessus.

public static class ProgTrad {
    int[] mem = new mem[1000];
    Stack<Integer> stack = new Stack<>();
    int ic = 0;

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
                case 0: stack.push(ic); ic = 100; break;
                case 1: stack.push(ic); ic = 200; break;
                case 2: System.exit(0); break;

                case 100: System.out.println("Dans la fonction f"); break;
                case 101: ic = stack.pop(); break;

                case 200: System.out.println("Dans la fonction g"); break;
                case 201: stack.push(ic); ic = 100; break;
                case 202: System.out.println("Fin de la fonction g"); break;
                case 203: ic = stack.pop(); break;
            }
        }
    }
}

Quelques remarques:

Quand on écrit stack.push(ic), grâce à la post-incrémentation, ic contient ici l'adresse de l'instruction suivante, ce qui est bien ce qu'on veut.

La convention dans ce cours est de bien séparer les adresse de chaque fonction, par exemple en disant que chaque fonction correspond à un chiffre des centaines comme dans l'exemple précédent.

Passer des arguments aux fonctions

Quand on apelle un fonction, par exemple:

pow(2, 20)

on passe deux informations supplémentaires à la fonction pow, en plus de l'adresse de retour comme on l'a vu précédemment : la valeur des deux arguments, 2 et 20 dans ce cas.

Pour ce faire, on utilise aussi pile d'exécution. Dans le cas présent, au lieux de n'empiler que l'adresse adresse, on empile ces trois valeurs en même temps. Ainsi, au lieux de contenir des entiers, la pile d'exécution va contenir des blocs. Dans ce cas là, un bloc est une classe contenant trois champs:

class Block {
    public int ric;  // adresse de retour
    public int arg0; // premier argument
    public int arg1; // deuxième argument

    public Block(int r, int a0, int a1) {
        ric = r;
        arg0 = a0;
        arg1 = a1;
    }
}

et la pile sera une pile de tels blocs:

Stack<Block> pile = new Stack<>();

Dans la traduction, la fonction pourra accéder à ses argument avec

pile.peek().arg1

et à l'adresse de retour soit avec peek soit avec pop:

pile.pop().ric

Au niveau de l'appel de fonction, il suffit de changer ce qu'on empile:

pile.push(new Block(ic, 2, 20));

Les appels de fonctions avec des arguments est l'objet du TD 5.

La suite

Dans la suite, on va apprendre à gérer:

  1. les variables locales aux fonctions,

Exercices

Pour la prochaine fois, préparer les deux exercices du TD4 et ceux du TD5 (pas besoin d'annoter).

Vous pouvez vous aider de ce rappel de cours.

Correction du TD4

Exercice 1

public class BasiqueTrad {
	public static void main(String[] args) {
		int ic=0;
		int[] mem=new int[1000];
		Stack<Integer> p=new Stack<Integer>();
		while (true) {
			switch (ic++) {
				case 0: System.out.println("Entrée main"); break;
				case 1: p.push(ic); ic=300; break;
				case 2: p.push(ic); ic=100; break;
				case 3: System.out.println("Sortie main"); break;
				case 4: System.exit(0);
				
				case 100: System.out.println("Entrée h"); break;
				case 101: p.push(ic); ic=200; break;
				case 102: System.out.println("Sortie h"); break;
				case 103: ic=p.pop(); break;
				
				case 200: System.out.println("Entrée g"); break;
				case 201: p.push(ic); ic=300; break;
				case 202: System.out.println("Sortie g"); break;
				case 203: ic=p.pop(); break;
				
				case 300: System.out.println("Milieu f"); break;
				case 301: ic=p.pop(); break;
			}
		}
	}
}

Exercice 2

public class Partiel2018Trad {
	public static void main(String[] args) {
		int ic=0;
		int[] mem=new int[1000];
		Stack<Integer> p=new Stack<Integer>();
		while (true) {
			switch (ic++) {
				case 0: mem[0] = 0; break;
				case 1: mem[2] = 20; break;
				case 2: mem[3] = 20; break;
				case 3: p.push(ic); ic = 300; break;
				case 4: if (mem[0]>4) ic += 3; break;
				case 5: p.push(ic); ic = 100; break;
				case 6: p.push(ic); ic = 300; break;
				case 7: ic -= 4; break;
				case 8: System.exit(0);
				
				case 100: System.out.println(" début tirs"); break;
				case 101: mem[1] = 1; break;
				case 102: if (mem[1]>5) ic += 3; break;
				case 103: p.push(ic); ic = 200; break;
				case 105: mem[1]++; break;
				case 106: ic -= 4; break;
				case 107: System.out.println(" fin tirs"); break;
				case 108: ic = p.pop(); break;
				
				case 200: System.out.println("  cible " + mem[1]); break;
				case 201: mem[3]--; break;
				case 202: ic=p.pop(); break;
				
				case 300: mem[0]++; break;
				case 301: System.out.println("dans le tour " + (mem[0])); break;
				case 302: mem[2] -= 4; break;
				case 303: ic = p.pop(); break;
			}
		}
	}
}

Adapté de la solution de Maryline Z.