CI2 Groupe INFO5 - Partie 2

14 Avril 2020

Introduction

Vous devriez maintenant avoir accès aux capsules 3 et 4 du cours, portant sur la traduction d'appels de fonctions avec arguments et valeurs de retour.

Ce deuxième article commence par quelques rappels sur certaines questions que j'ai pu avoir, ainsi qu'une correction d'un exercice du TD3 et d'un exercice du TD4, afin de vous aider à avancer. Ensuite, vous trouverez des notes de cours contenant mon interprétation personnelle sur la traduction des appels de fonctions avec arguments et valeurs de retour.

N'oubliez pas qu'un serveur Discord est disponible pour poser vos questions et interagir ! Vous devriez normalement avoir reçu le lien par e-mail, mais vous pouvez toujours me le redemander si nécessaire.

Rappels sur la traduction de tableaux

Je voudrais revenir dans un premier temps sur la traduction des tableaux, car c'est quelque chose que vous aurez à faire fréquemment, et un point important de la compilation. La traduction comporte deux aspects : la déclaration (allocation) des tableaux, et les accès aux tableaux.

Déclaration

Vous avez vu lors des deux premiers TD qu'un tableau n'est rien d'autre qu'une suite de cases mémoire. Allouer un tableau, via par exemple int[] t = new int[20], revient à « réserver » un bloc de 20 cases dans la mémoire pour y stocker des entiers. Ensuite, un accès à t[4] par exemple, revient à aller chercher la cinquième case (n'oubliez pas que la première case est à l'indice 0) de ce bloc.

La traduction suit le même principe : allouer un tableau d'entiers de taille 20 revient à décider de 20 cases mémoires où mettre des entiers. Tout comme une déclaration sans affectation d'une variable, c'est une décision que vous prenez en annotant le programme à traduire, et qui ne correspond pas à une instruction dans le programme traduit. En effet, la mémoire est déjà allouée au début de votre programme via int[] mem = new int[100000]. Écrire une instruction qui alloue un tableau dans cette mémoire n'aurait aucun sens (sans compter que je n'ai aucune idée de comment écrire une instruction pareille). Vous avez donc juste à décider que, par exemple, les cases de mem[4] à mem[23] correspondent à votre tableau de 20 cases. Attention à bien compter les cases ! Par exemple, mem[0..19] fait bien 20 cases !

À titre d'exemple, considérez l'extrait à traduire suivant :

int a;
int[] t = new int[10];
int b = 4;

Cet extrait contient trois choses distinctes.

une déclaration de variable int a sans affectation, qui ne correspondra donc à aucune instruction dans le programme mais qui doit être annotée afin de choisir un emplacement mémoire pour la variable a.
une déclaration de tableau int[] t = new int[10], qui, comme pour l'instruction précédente, ne correspondra à aucune instruction dans le programme. Cependant, vous devez aussi l'annoter afin de choisir 10 emplacements mémoire pour le tableau t.
enfin, une déclaration avec affectation de variable int b = 4. Le plus simple est de voir cette instruction comme deux instructions en séparant la déclaration de l'affectation comme ceci :
```
int b;
b = 4;
```
Ainsi, la déclaration peut être traitée comme le premier point, et l'affectation correspond, comme d'habitude, à une instruction dans le programme traduit.

En résumé, le programme peut être annoté comme ceci :

int a;                 // a = mem[0]
int[] t = new int[10]; // t = mem[1..10]
int b = 4;             // b = mem[11], affectation case 0

et la traduction ne comporterait qu'une seule instruction, celle pour l'affectation, comme ceci :

case 0: mem[11] = 4; break;

Notez que j'ai choisi d'allouer les cases dans l'ordre, ainsi, le tableau prend les 10 premières cases disponibles (donc les cases de 1 à 10, puisque la case 0 contient déjà a).

Accès

Maintenant que vous savez comment traduire (ou plutôt, ne pas traduire) la déclaration de tableaux, il reste à comprendre comment traduire les accès aux tableaux.

Comme beaucoup de choses dans la traduction de programmes, la traduction des accès aux tableaux peut-être faite de manière très mécanique (et je vous encourage à y penser de cette façon, si cela vous aide) pour peu que vous ayez bien annoté votre programme.

Reprenez l'exemple précédent : notre tableau t prend 10 cases mémoire, et nous avons décidé que ces cases seraient les cases mem[1] à mem[10]. Sachant cela, comment traduire un accès à t[0] ? Et bien, un tel accès revient à accéder à la première case de notre tableau, donc celle que nous avons décidé être mem[1]. Un accès à t[1] est un accès à la deuxième case, donc mem[2].

Si vous continuez un peu comme ça, vous remarquerez qu'un accès à la case i via t[i] est traduit par un accès à la case mémoire mem[1+i]. Vous pouvez donc traduire mécaniquement tous les accès à t dans votre programme. Par exemple, si votre programme contient l'extrait suivant (annoté un peu au pif) :

t[0] = 4; // case 5
t[3] = 5; // case 6
t[b] = 2; // case 7, n'oubliez pas que b est mem[11]

alors vous pouvez traduire ça directement en :

case 5: mem[1+0] = 4; break;
case 6: mem[1+3] = 5; break;
case 7: mem[1+mem[11]] = 2; break;

Vous remarquerez que j'ai bêtement appliqué la traduction t[i] -> mem[1+i] sans calculer la somme, mais vous pouvez bien sûr remplacer 1+0 par 1 et 1+3 par 4, si vous préférez.

Et si le tableau ne commence pas en mem[1] ?

La traduction t[i] -> mem[1+i] ne fonctionne que parce que le tableau commence en mem[1]. En effet, si vous refaites le raisonnement précédent avec un tableau commençant, par exemple, en mem[3], vous remarquerez que l'accès t[0] est traduit par mem[3]. Plus généralement, l'accès à t[i] est traduit par mem[3+i].

Donc, de manière générale, si votre tableau commence en mem[n] alors l'accès à t[i] est traduit par mem[n+i].

Application (TD 3, exercice 4)

Afin d'appliquer tout ça, je vous propose de corriger l'exercice 4 du TD3. Tout d'abord, voici comment il est possible d'annoter le programme. Vous remarquerez que le tableau est déclaré avant tout le reste, donc j'ai choisi de le placer très simplement au tout début de la mémoire. Et donc, si vous avez bien compris mon pavé précédent, l'accès à t[i] sera simplement traduit par un accès mem[0+i], ou encore par mem[i] (par un procédé arithmétique extraordinaire).

public static void main(String[] arg) {
  int[] t = new int[20];                      // t = mem[0..19], pas d'instruction !
  t[0] = 1;                                   // case 0
  t[1] = 1;                                   // case 1
  for(int i = 2;                              // i = mem[20], affectation case 2
          i < 20;                             // case 3
          i++)                                // case 5, annoté après avoir annoté le corps de la boucle
    t[i] = 2 * t[i-1] + t[i-2];               // case 4
                                              // case 6, n'oubliez pas l'accolade qui devrait se trouver là 
                                              //         pour fermer la boucle
  System.out.println("Nombre(19) =" + t[19]); // case 7
}                                             // case 8, exit

Une fois le programme annoté, il peut être traduit mécaniquement comme ceci :

class ProgTrad {

  public static void main(String [] args) {

    // Déclaration du compteur d'instruction et de la mémoire (pas de pile ici)
    int ic = 0;
    int mem[] = new int[100000];

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

Correction TD 4, exercice 1

Voici une correction possible de l'exercice 1 du TD4, pour vous aider à avancer. Comme d'habitude, n'hésitez pas à me poser des questions sur cette correction si vous en avez. Je vous invite aussi à lire l'article précédent, qui portait sur les appels de fonctions basiques.

Je propose l'annotation suivante. Le main commence en 0, la fonction f en 100, g en 200 et h en 300. Vous êtes bien entendu libres de choisir d'autres valeurs, tant que les indices au sein d'une même fonction sont successifs.

class Basique {
  static void h(){
    System.out.println("Entrée h"); // case 300
    g();                            // case 301
    System.out.println("Sortie h"); // case 302
  }                                 // case 303

  static void g(){
    System.out.println("Entrée g"); // case 200
    f();                            // case 201
    System.out.println("Sortie g"); // case 202
  }                                 // case 203

  static void f(){
    System.out.println("Milieu f"); // case 100
  }                                 // case 101

  public static void main(String[] args ){
    System.out.println("Entrée main"); // case 0
    f();                               // case 1
    h();                               // case 2
    System.out.println("Sortie main"); // case 3
  }                                    // case 4
}

La traduction du programme est alors la suivante.

class BasiqueTrad {

  public static void main(String [] args) {

    int ic = 0;
    int mem[] = new int[100000];  // En fait la mémoire n'est pas nécessaire ici
    Stack<Integer> stack = new Stack<Integer>();

    while (true) {
      switch (ic++) {

        // Fonction main
        case 0: System.out.println("Entrée main"); break;
        case 1: stack.push(ic); ic = 100; break;
        case 2: stack.push(ic); ic = 300; break;
        case 3: System.out.println("Sortie main"); break;
        case 4: System.exit(0);

        // Fonction f
        case 100: System.out.println("Milieu f"); break;
        case 101: ic = stack.pop(); break;

        // Fonction g
        case 200: System.out.println("Entrée g"); break;
        case 201: stack.push(ic); ic = 100; break;
        case 202: System.out.println("Sortie g"); break;
        case 203: ic = stack.pop(); break;

        // Fonction h
        case 300: System.out.println("Entrée h"); break;
        case 301: stack.push(ic); ic = 200; break;
        case 302: System.out.println("Sortie h"); break;
        case 303: ic = stack.pop(); break;

      }
    }
  }
}

Traduction des fonctions avec environnement et valeurs de retour

Stockage des valeurs des paramètres

Commençons par le cas (un peu plus simple) des fonctions sans valeur de retour. Lorsqu'on écrit une fonction avec des paramètres, c'est pour, a priori, donner des valeurs à ces paramètres lors de l'appel de la fonction, et y accéder dans le corps de cette fonction. C'est sur ces deux points que se concentre la traduction des appels de fonction avec environnement.

Intéressons nous d'abord à la manière de passer des valeurs lors de l'appel d'une fonction. Ces valeurs peuvent changer d'un appel à l'autre, ainsi, il est impossible de les inclure directement dans le corps de la fonction. Il faut, lors de l'appel à la fonction, que le programme stocke les valeurs à un endroit accessible par la fonction, afin qu'elle puisse y accéder.

Nous n'avons que deux endroits où stocker des valeurs dans une traduction : la pile stack et le tas mem. Lequel choisir ? La bonne solution est d'utiliser la pile. Pour bien comprendre, remarquez que, si on stockait les valeurs des paramètres dans le tas, il faudrait quand même que la fonction sache où chercher ces valeurs dans le tas. Sachant que cet endroit peut changer à chaque appel, il faudrait quand même lui communiquer l'adresse de la valeur dans le tas en argument. Ça paraît être une boucle sans fin, non ?

Si cela ne vous convainc pas parfaitement, vous pouvez aussi remarquer que la valeur d'un paramètre est très éphémère et n'est utile que pendant l'appel à la fonction. Quoi de mieux donc qu'utiliser la pile, puisque son but est justement de stocker une valeur (jusqu'à maintenant la valeur de ic) pendant l'appel d'une fonction, et d'être vidée ensuite ?

Pour résumer, lors d'un appel de fonction, il faut non seulement empiler la valeur de ic à laquelle retourner après l'appel, mais aussi la valeur des paramètres de la fonction. Pour cela on va créer des « blocs », qui sont des classes contenant les informations nécessaires. Par exemple, pour la fonction suivante (dont on ignore pour l'instant le corps) :

static void f(int x, int y) {
  ...
}

il nous faut un bloc contenant ic comme toujours, mais aussi les valeurs de x et y. Ainsi, au tout début de la traduction, il faut donc créer la classe suivante :

class BlockA {
    int arg0;  // valeur de x pour la fonction f
    int arg1;  // valeur de y pour la fonction f
    int ric;   // valeur de ic à laquelle retourner après l'appel

    public BlockA(int arg0, int arg1, int ric) {
        this.arg0 = arg0;
        this.arg1 = arg1;
        this.ric = ric;
    }
}

Comme ce bloc peut éventuellement être réutilisé pour d'autre fonctions avec deux paramètres de type int avec éventuellement des noms de paramètres différents; on préférera nommer les variables correspondant aux arguments de manière flexible, comme ici par exemple arg0, arg1, etc... Vous remarquerez aussi qu'on crée un constructeur (public BlockA(...)) qui facilite la création d'un bloc avec les valeurs voulues.

Il faut aussi changer la déclaration de la pile afin que celle-ci ne stocke plus uniquement des entiers, mais des blocs complets :

Stack<BlockA> stack = new Stack<BlockA>();

Traduction des appels

Maintenant que vous savez créer un bloc contenant les données nécessaires à la fonction, et que vous avez adapté la pile pour contenir ces blocs, il est possible de passer à la traduction des fonctions. Je vous rassure, le plus gros du travail est fait, et la traduction est assez mécanique (comme d'habitude).

La traduction des appels ne change pas beaucoup par rapport à avant. Jusqu'à maintenant, on empilait simplement la valeur de ic puis on faisait un saut, en modifiant ic. Le saut ne change pas, en revanche, il nous faut maintenant empiler un bloc complet. Considérons l'extrait (partiellement annoté) suivant :

static void f(int x, int y) {
  ...       // on suppose que f commence au case 100
}

public static void main(String[] args) {
  f(3, 5);  // case 0
}

Sachant que nous pouvons créer un bloc à l'aide de new BlockA(arg0, arg1, ric), il suffit de substituer les bonnes valeurs pour arg0, arg1, et ric et d'empiler le bloc pour traduire le case 0 comme ceci :

case 0: stack.push(new Block(3, 5, ic)); ic = 100; break;

Et voilà, il n'y a rien de plus à faire pour traduire un appel !

Traduction des fonctions avec paramètres

La traduction du corps des fonctions change aussi un peu, puisque ces dernières peuvent maintenant accéder aux valeurs de leurs paramètres. Il faut donc aller chercher ces valeurs dans le bloc au sommet de la pile (puisque, si vous vous souvenez des premiers TD, le bloc au sommet est toujours celui de l'appel courant). Pour aller chercher une valeur dans le bloc sans le dépiler (on ne veut le dépiler qu'à la fin de la fonction), on utilisera l'instruction stack.peek() qui renvoie le sommet de la pile sans le dépiler.

Ainsi, si on reprend la fonction précédente :

static void f(int x, int y) {
  System.out.println(x + y);   // case 100
}                              // case 101

l'accès à x reviendra à aller chercher la valeur de arg0 dans le premier bloc de la pile, c'est à dire via stack.peek().arg0, et de même pour y avec arg1. N'oubliez pas, comme d'habitude, de dépiler le bloc et de restorer ic (à la valeur de ric dans le bloc) dans le case 101. La traduction de cette fonction serait donc :

case 100: System.out.println(stack.peek().arg0 + stack.peek().arg1); break;
case 101: ic = stack.pop().ric; break;

Cas des fonctions avec valeur de retour

Nous avons vu jusqu'à maintenant le cas des fonctions sans valeur de retour, il nous reste juste à ajouter cette possibilité. Mais, encore une fois, le plus dur est fait. :-)

Lors d'un appel, l'appelant doit transmettre des informations à la fonction appelée. Ici, c'est l'inverse : la fonction doit transmettre des informations (la valeur de retour) à l'appelant. On va utiliser le même principe, c'est à dire ajouter l'information à la pile, dans laquelle l'appelant pourra lire.

Considérons donc la fonction suivante :

static int f(int x, int y) {
  return (x+y);
}

Nous allons simplement enrichir le bloc précédent pour y ajouter la valeur de retour, comme ceci :

class BlockA {
    int arg0;
    int arg1;
    int ric;
    int ret; // valeur de retour

    public BlockA(int arg0, int arg1, int ric) {
        this.arg0 = arg0;
        this.arg1 = arg1;
        this.ric = ric;
    }
}

Remarquez que nous n'avons pas enrichi le constructeur public BlockA(...), car, en effet, la valeur de retour est inconnue à la création du bloc ! Elle ne sera connue qu'à la fin de l'appel. C'est au moment de renvoyer la valeur que la fonction va stocker celle-ci dans le bloc.

Nous pouvons donc maintenant traduire f... Ou pas. Si vous y avez déjà réfléchi (ou si vous avez vu les capsules vidéo), vous avez sûrement remarqué un problème. En effet, jusqu'ici, nous avons traduit les fonctions afin qu'elles dépilent le bloc au sommet de la pile à la fin de l'appel, avant de restorer ic. Mais comment l'appelant peut-il accéder à la valeur de retour si le bloc a été dépilé par la fonction ? Il va falloir changer ça, afin que l'appelant dépile lui-même le bloc après l'appel, et après avoir traité la valeur de retour.

Attention, ceci implique que l'appel d'une fonction prenne systématiquement deux instructions (l'appel et le dépilement), pour une seule ligne de code.

Pour bien comprendre, prenez le code suivant, annoté de manière à ce que l'appel prenne deux instructions :

static int f(int x, int y) {
  return (x+y);              // case 100, affectation de ret
}                            // case 101, restoration de ic

public static void main(String[] args) {
  int a;                     // mem[0]
  a = f(3,5);                // case 0 (appel), case 1 (dépilement et affectation)
  System.out.println(a);     // case 2
}                            // case 3

alors la traduction complète serait :

class BlockA {
    int arg0;
    int arg1;
    int ric;
    int ret;

    public BlockA(int arg0, int arg1, int ric) {
        this.arg0 = arg0;
        this.arg1 = arg1;
        this.ric = ric;
    }
}

class ProgTrad {

  public static void main(String [] args) {

    int ic = 0;
    int mem[] = new int[100000];
    Stack<BlockA> stack = new Stack<BlockA>();

    while (true) {
      switch (ic++) {
        // fonction main
        case 0: stack.push(new BlockA(3,5,ic)); ic = 100; break;
        case 1: mem[0] = stack.pop().ret; break; /// c'est maintenant qu'on dépile le bloc !
        case 2: System.out.println(mem[0]); break;
        case 3: System.exit(0);

        // fonction f
        case 100: stack.peek().ret = stack.peek().arg0 + stack.peek().arg1; break;
        case 101: ic = stack.peek().ric; break;
      }
    }
  }
}

C'est fini (ouf) ! Avec ceci et les capsules, je pense que vous êtes équipé·e·s pour traduire des tas d'appels de fonctions avec ou sans arguments et valeurs de retour.

Il est aussi fort possible que j'aie fait des erreurs, donc n'hésitez pas à me faire part de vos doutes éventuels.

Exercices

Vous pouvez maintenant faire les exercices du TD5, qui comportent des fonctions avec arguments et valeurs de retour. Si vous voulez commencer par vous entraîner avec des exercices un peu plus simples, je vous recommande de regarder les petites fonctions qui accompagnent les capsules vidéos sur Moodle.

Bien sûr, n'hésitez pas à poser vos questions ou à faire partager vos corrections sur Discord ou par e-mail, selon vos préférences !