CI2 Groupe INFO5 - Partie 1

23 Mars 2020

Introduction

Cette section du site contient un ensemble de notes et d'exercices permettant de poursuivre les TD du cours de Concepts Informatiques de L1 à l'Université de Paris. Ces notes s'adressent en priorité au groupe INFO5, mais peuvent bien sûr être réutilisées librement.

Dans l'idéal, ces notes devraient pouvoir permettre à chacun·e de poursuivre l'apprentissage du cours de CI2 au rythme qui lui convient, et ce malgré le confinement actuellement en place. Il n'y a ainsi aucune obligation de compléter tous les exercices chaque semaine pour les étudiant·es n'y étant pas disposé·es.

Chaque semaine (idéalement chaque mercredi aux heures de TD), j'ajouterai à cette section du site une page avec des notes et exercices supplémentaires.

Les étudiant·es qui le souhaitent sont libres de (et encouragé·es à) m'envoyer leurs solutions et questions par email. Vu les circonstances, je répondrai encore plus rapidement que d'habitude. :-)

Bien entendu, je suis ouvert à toute critique portant sur ma manière de poursuivre cet enseignement, ainsi que sur le contenu de ces pages.

Rappels sur la traduction de programmes

Pourquoi traduire des programmes ?

La majorité des exercices que vous aurez à faire ce semestre consiste à traduire des programmes Java vers un sous-ensemble limité de Java.

En tant que programmeur, il est en général préférable (pour son bien-être général) de coder dans un langage dit de haut niveau, tel que Java, C++, et bien d'autres. Un tel language est (relativement) facilement compréhensible par un programmeur, mais n'est pas fait pour être immédiatement compris par une machine. C'est ici qu'interviennent les compilateurs, dont la tâche est de produire du code compréhensible par un ordinateur à partir du code produit par le programmeur.

Le but du cours de CI2 est de vous fournir une introduction à la compilation. Cependant, en général, le langage machine vers lequel les compilateurs traduisent est complexe est peu lisible (voir des exemples de langage assembleur). Plutôt que de vous faire apprendre un tel langage, on préfèrera donc traduire vers un fragment de Java, stylisé de manière à ce que le code produit s'approche de ce que pourrait produire un compilateur.

Principe

Comme nous l'avions déjà vu en TD, la forme globale du code que vous devez produire lors d'une traduction est toujours la même. Le squelette, que vous pouvez noter et garder précieusement, est celui-ci.

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;
        ...

      }
    }
  }
}

Les deux seules parties à modifier sont :

la déclaration de la mémoire, par exemple pour ajouter une pile (voir la section sur les appels de fonctions), ou si on vous demande explicitement d'y déclarer des variables;
la liste des instructions, qui représente la majeure partie de votre travail de traduction.

Les instructions devront être aussi simples que possible. De manière générale, on s'autorisera les expressions suivantes :

affectation de type mem[e1] = e2; où e1 et e2 sont des expressions arithmétiques simples;
modification immédiate du pointeur d'instruction ic = e; où e est une expression arithmétique simple;
saut conditionnel if (test) ic = e; où test et e sont des expressions simples;
fin du programme System.exit(0).

En particulier, les boucles ainsi que les expressions conditionnelles portant sur autre chose qu'une modification du pointeur d'instruction sont interdites.

Méthodologie

Le conseil le plus important que je peux vous donner est le suivant : une traduction peut toujours être faite de manière automatique.

Rappelez-vous que la traduction est, normalement, le travail d'un compilateur. Sans trop entrer dans des considérations métaphysiques, un compilateur n'étant a priori pas doté de libre arbitre, la traduction est un procédé très mécanique lors duquel les seuls choix que vous devriez avoir à faire sont des choix stylistiques.

Ainsi, si vous appliquez la méthodologie suivante étape par étape, vous devriez toujours parvenir à traduire les programmes qui vous sont donnés.

Commencez par identifier toutes les variables définies dans le programme. Donnez à chacune une position unique en mémoire, et notez celle-ci à côté de la variable. Rappelez-vous qu'un tableau de taille 100 prend 100 places en mémoire ! Voici un exemple d'annotations :
```
int k;                    // mem[0]
int[] tab = new int[100]; // mem[1-100] (il faut ici 100 cases)
int a;                    // mem[101] (la case 101 est la prochaine case disponible)
int[] tab2 = new int[5];  // mem[102-106] (il faut ici 5 cases)
```
Annotez chaque instruction du programme, dans l'ordre, avec son numéro d'instruction. Dans le cas des boucles for, rappelez-vous que l'instruction for contient trois instructions, et que la troisième doit être faite à la fin de la boucle. Je vous conseille de l'indiquer clairement afin de ne pas l'oublier à la fin, et d'ajouter son numéro d'instruction plus tard après avoir annoté le reste.
Attention, rappelez-vous aussi qu'il faut une instruction supplémentaire à la fin d'un if si un else est présent, ainsi qu'à la fin d'une boucle. Personnellement, j'aime bien voir le else et l'accolade fermante de fin de boucle comme des instructions. Voici un exemple d'annotations (d'un programme absolulment stupide) sur ce principe :
```
int k = 0;     // case 0, mem[0]
for(int i = 0; // case 1, mem[1]
        i < 5; // case 2
        i++)   // case 7 (doit venir avant l'instruction de l'accolade de fin)
{ 
  if(i >= 3)   // case 3
    k = k + i; // case 4
  else         // case 5 (ne pas oublier le else)
    k = k - i; // case 6
}              // case 8
               // case 9 (fin du programme)
```

Afin de limiter les possibilités d'erreurs, vous pouvez ajouter aux annotations précédentes les sauts (i.e. modifications du compteur ic) à effectuer. Il faut un saut par if, par else, ainsi que par début et fin de boucle.

Le programme précédent deviendrait alors :

int k = 0;     // case 0, mem[0]
for(int i = 0; // case 1, mem[1]
        i < 5; // case 2, saut en 9 si le test échoue
        i++)   // case 7
{ 
  if(i >= 3)   // case 3, saut en 6 si le test échoue
    k = k + i; // case 4
  else         // case 5, saut en 7 (après le else)
    k = k - i; // case 6
}              // case 8, saut en 2 (pour refaire un tour de boucle)
               // case 9

Une fois cela fait, vous pouvez recopier le squelette précédent et remplir les cas, en prenant soin de bien convertir les accès aux variables en accès à la mémoire. Rappelez-vous que l'instruction switch(ic++) incrémente ic mais exécute le cas correspondant à l'ancienne valeur du compteur. Ainsi, lorqu'on exécute le cas N, ic vaut N+1. La conséquence principale est que pour sauter du cas 8 au cas 2 dans le programme précédent, il faut enlever 7 à ic (9 - 2 = 7).

Le programme précédent deviendrait ainsi :

class ProgTrad {

  public static void main(String[] args) {

    int ic = 0;
    int mem[] = new int[100000];

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

Fonctions et appels de fonctions

Un peu de théorie

De la même façon qu'une condition ou qu'une boucle, un appel de fonction correspond à un saut dans le programme. Cependant, là où une condition se contente de sauter une partie du programme avant de continuer à l'exécuter, un appel de fonction doit être capable de retourner à la position de l'appel une fois que la fonction a fini de s'exécuter.

Il faut donc, lors de l'appel d'une fonction, stocker la position de l'appel afin de pouvoir y retourner. Mais que se passe-t-il si la fonction appelée en appelle une autre ? Il faut aussi stocker la position de cet appel. Et ce procédé peut s'enchaîner un très grand nombre de fois (jusqu'à ce que votre programme finisse par crasher).

Lorsque les fonctions finissent leur exécution, il faut ensuite retourner successivement à la position de chaque appel, sachant que la première fonction à terminer sera la dernière appelée. Vous commencez à voir quelle structure utiliser pour stocker les adresses de retour ? Sinon, le fait qu'on ait fait deux TD sur les piles devrait vous aider. :-)

Donc pour résumer, chaque programme a une pile d'exécution. Lorsque vous faites un appel de fonction, le programme stocke sur cette pile ce qu'on appelle une frame, qui est en gros une structure regroupant les informations nécessaires au bon déroulement de l'appel et à son retour.

Pour le moment, on considèrera que la seule chose dont on a besoin est l'adresse de retour, une pile d'entiers suffira donc.

Traduction

Intéressons-nous maintenant à la traduction des fonctions et des appels de fonctions. Comme je l'ai indiqué dans le paragraphe précédent, il va nous falloir une pile, pour l'instant ne contenant que des entiers, qui correspondront aux adresses de retour. Vous pouvez donc enrichir le squelette de la traduction comme suit :

class ProgTrad {

  public static void main(String [] args) {

    // Déclaration du compteur d'instruction, de la mémoire *et de la pile*
    int ic = 0;
    int mem[] = new int[100000];
    Stack<Integer> stack = new Stack<Integer>();

    ...

Il va aussi falloir ajouter des instructions de base afin de manipuler cette pile. Les deux seules dont vous aurez besoin pour le moment sont :

stack.push(ic) qui place la valeur actuelle du compteur d'instruction sur la pile afin de pouvoir y retourner plus tard;
ic = stack.pop() qui restore la valeur du compteur d'instruction à la valeur dernièrement sauvegardée.

Pour bien comprendre comment ces instructions fonctionnent, prenez par exemple l'extrait de programme suivant, partiellement annoté avec des numéros d'instructions arbitraires :

public static void f() {
  System.out.println("C'est moi");        // cas 10
}

public static void main(String [] args) {
  System.out.println("Salut");            // cas 0
  f();                                    // cas 1
  System.out.println("Au revoir");        // cas 2
}

Les cas 0, 2 et 10 sont faciles : ce sont juste des appels à System.out.println. En revanche, le cas 1 est un appel de fonction. Il faut qu'une fois que f a fini de s'exécuter, elle soit capable de continuer l'exécution du programme au cas 2. C'est pour cela qu'au moment de l'appel, c'est à dire dans le cas 1, on va ajouter sur la pile la valeur actuelle du compteur ic (qui vaudra 2, si vous vous souvenez du discours sur switch(ic++)), puis aller au cas 10.

Ensuite, lorsque f aura fini son exécution (c'est à dire après le cas 10), il suffira qu'elle dépile la valeur au sommet de la pile pour savoir où sauter.

S'en suivent deux remarques.

Un appel de fonction consiste en fait en deux instructions. Une plaçant le compteur d'instruction sur la pile (afin de pouvoir y retourner), puis une modifiant ce compteur afin d'aller à la première instruction de la fonction. Pour éviter des erreurs dans le comptage des cas, on s'autorisera en fait à fusionner ces deux instructions en un seul cas, qui deviendra donc stack.push(ic); ic = n; où n est l'entier correspondant à la première instruction de la fonction appelée.
De la même façon qu'à la fin du main il faut compter un cas pour terminer le programme avec System.exit(0), il faut ajouter un cas à la fin de chaque fonction auxiliaire afin de retourner à la position de l'appel. Comme pour les boucles et conditions, j'aime bien compter l'accolade fermante comme un cas.

Si on annote complètement le programme précédent, il devient donc :

public static void f() {
  System.out.println("C'est moi");        // cas 10
}                                         // cas 11 (retour à l'appel)

public static void main(String [] args) {
  System.out.println("Salut");            // cas 0
  f();                                    // cas 1
  System.out.println("Au revoir");        // cas 2
}                                         // cas 3 (exit)

Et la traduction serait :

class ProgTrad {

  public static void main(String [] args) {

    // Déclaration du compteur d'instruction, de la mémoire et de la pile
    int ic = 0;
    int mem[] = new int[100000];
    Stack<Integer> stack = new Stack<Integer>();

    while (true) {
      switch (ic++) {
        // Fonction main
        case 0: System.out.println("Salut"); break;
        case 1: stack.push(ic); ic = 10; break; // Saut à l'instruction 10, fonction f
        case 2: System.out.println("Au revoir"); break;
        case 3: System.exit(0);

        // Fonction f
        case 10: System.out.println("C'est moi"); break;
        case 11: ic = stack.pop(); break; // Reprise du programme à l'instruction stockée
      }
    }
  }
}

Un dernière remarque : vous remarquerez que j'ai choisi de commencer la fonction f au cas 10, plutôt qu'au cas 4. C'est arbitraire et vous pouvez en fait choisir de commencer une fonction à n'importe quelle adresse. Cependant, si vous choisissez des adresses éloignées, cela vous permet de ne pas avoir à tout re-numéroter si vous vous rendez compte que vous avez oublié un cas, ou si vous ajoutez une ligne de code dans une fonction. Par exemple, je peux ici facilement ajouter 6 instructions au main sans tout avoir à re-numéroter.

Ainsi, je vous conseille d'annoter vos fonctions avec des adresses suffisamment distantes, par exemple en commençant main à 0, la première fonction à 100, la deuxième à 200, etc...

Et voilà, avec tout ça, vous voilà (je l'espère) équipé·es pour faire les exercices qui suivent ! Bien sûr, au risque de me répéter, si vous avez la moindre question ou remarque n'hésitez pas à me contacter. C'est important que vous compreniez ce que j'écris, et j'ai conscience que ça n'est pas toujours clair, malgré tous mes efforts. :-)

Exercices

Tout d'abord, assurez vous d'avoir bien compris les traductions du TD3 que nous avions vu en TD. Je vous encourage à les refaire en vous aidant des rappels précédents, et à m'envoyer vos éventuelles questions.

Ensuite, vous pouvez faire les exercices du TD4. Ces exercices portent sur la traduction d'appels de fonctions. Le premier consiste en un programme très basique dont le but est surtout de vous faire comprendre comment et dans quel ordre les fonctions sont évaluées par Java. Le second est un peu plus complexe car il manipule quelques variables, mais le principe reste le même.

Rappelez vous que vous pouvez traduire le corps de chaque fonction de manière indépendante, de la même façon que pour les programmes du TD3.