:: Enseignements :: Master :: M2 :: 2014-2015 :: Machine Virtuelle (et bazard autour ...) ::

Lab 2 - Stack Interpreter

Ce second lab est découpé en 3 parties, dans un premier temps, nous allons nous intéresser à l'implantation de l'interpreteur en écrivant les instructions des fonctions à la main puis dans un second temps, nous implanterons un visiteur qui à partir de l'AST est cpable de générer les instructions d'une fonction. Enfin, dans le but de detecter les stackoverflow, nous modifierons le visteur pour calculer la taille maximal de la pile nécessaire pour exécuteur chaque fonction.
Une base de code est disponible: vm2015-lab2.zip

Exercice 1 - Stack interpreter

Voici une video de Terence Parr de l'université de San Franscisco qui illustre les différents principes de contruction d'un interpreteur à pile.
How to Build a Virtual Machine par Terence Parr

Le but de cet exercice est d'écrire un interpreteur à pile correspondant à un script du language Scipr.

On cherche dans u premier temps à comprendre les rôles des classes
- Codes
- CodeMap
- Dictionary
- Instructions
- TagValues
- StackInterpreter
Commenter le code de Codes.main(Dictionnnary) et replacer le par un code qui affiche 42.
Que se passe t'il si on execute le code avec l'interpreteur ?
Faite en sorte que le code marche !
Modifier la méthode qui générère le code pour pouvoir exécuter le script suivant.
```
          a = 3
          print(a)
         
```
puis faite les modifications qui s'impose dans l'interpreteur

Vérifier que l'exécution de

          a = b = 3
          print(a)
          print(b)

se passe corectement.

Modifier l'interpreteur pour que le code suivant s'exécute correctement:
```
          print(2 + 3)
         
```
Faire de même avec les opérations '-' et '<' (unitaire).
Generer un code qui test l'instruction GOTO puis modifier l'interpreteur pour exécuter l'instruction GOTO.
Faire de même avec JUMP_IF_FALSE
On souhaite maintenant implanter l'appel de fonction (CALL et RET).
A quoi servent les variables BP_OFFSET, PC_OFFSET et CODE_OFFSET ?
Sachant que l'on veut que les arguments d'un appel de fonction corresponde aux paramètres de la fonction appelée sans faire de copie, comment doit être organisé la pile ? (faire un dessin !)
Comment detecter la fin du programme ?
Implanter l'appel de fonction.
Note: sauver la référence sur le code courant se fait grace au dictionnaire.

Exercice 2 - Rewriter

On cherche maintenant à pouvoir exécuter le script directement depuis la ligne de commande. Pour cela, nous allons dans un premier temps transformer le code des fonctions en instruction puis exécuter celle-ci.
Pour simplifier les choses, on va ré-écrire l'ensemble des fonctions en instructions avant d'exécuter celle-ci. Nous verrons dans un prochain lab comment ré-écrire le code uniquement lorsque l'on en a besoin.

Fait en sorte de pouvoir générer les instructions correspondant au code

         fn(main:
           print(42)
         )

Modifier le Rewriter pour pouvoir exécuter le code

         fn(main:
           a = 2
           print(a)
         )

Ajouter le code pour le support des addition, soustraction, etc et les comparaisons.
Ajouter le code de support des appels de fonctions.
Ajouter le code de support du 'if'.
L'idée consiste à laisser de la place pour la où le GOTO devrait sauter et de patcher la case mémoire à postériori.
Ajouter le code de suppport du while.

Exercice 3 - Calculer la taille maximale de la pile [pour aller plus loin]

On souhaite modiier la classe Rewriter pour calculer la taille maximale de la pile.
Pour cela ajouter les champs et méthodes suivantes dans la classe Rewriter.Env.

    private int currentStack;
    private int maxStack;   
       
    public void push() {
      currentStack++;
      maxStack = Math.max(maxStack, currentStack);
    }
    public void pop(int stackSize) {
      currentStack -= stackSize;
      assert currentStack >= 0;
    }
    public int getMaxStack() {
      return maxStack;
    }

Ajouter les appels à push et pop pour calculer la taille maximal de la pile pour chaque fonction.
Utiliser la taille maximale calculée à la question précédente pour vérifier que la pile est suffisamment grande (attention il faut aussi la place pour les variables locales) lors d'un appel de fonction.
Note: tester avec une toute petite pile.
Au lieu de lever une Failure si la pile est pleine, on souhaite afficher un stack trace. En reprenant le code de StackDumper écrire une méthode dans l'interpreteur qui calcul le stack trace.
On souhaite ajouter les numéros de ligne du script associée à chaque appel de fonction dans le stack trace. Pour cela, il faut associé un numéro de ligne à chaque instruction.
Proposer un algorithme qui permet d'associer un numéro de ligne à chaque instruction sans stocker un numéro de ligne pour chaque instruction.
Implanter l'algorithme.