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,