Lab 2b - Stack interpreter avec des objets

Exercice 1 - Avant propos (Préparation)

1. Ecrire le code permettant d'ajouter l'opération SWAP qui permute deux élements en sommet de pile, dans le Rewriter et dans le StackInterpreter.
2. Faire de même avec l'opération DUP_X1, qui duplique le sommet de pile et va l'insérer deux élements plus bas dans la pile.
3. Nous allons chercher à créer des objets, il nous faut pour cela un nouvel espace (le tas, ou heap en anglais) dans lequel il sera possible de stocker les objets les uns derrière les autres.
   Le code de la méthode interpret du StackInterpreter sera donc la suivante:

             public Object interpret(final Function main) {
               ByteBuffer code = this.code;
               IntBuffer stack = this.stack;
               ByteBuffer heap = this.heap;
               ConstantDictionnary dictionnary = this.dictionnary;
             

   Modifier votre main pour créer un tas de taille suffisant et modifier le code du StackInterpreter pour prendre en compte cette nouvelle zone de mémoire.
4. Comme on cré un nouveau type de valeur, il faut légèrement changer l'encodage de nos valeurs. En effet, il y a maintenant 3 types de valeurs. Les petits entiers, positif sur 31 bits, les index dans le constant dictionnary et les réferences vers des données dans le tas.
   L'encodage suivant va être utilisé:

               // xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxx1 -> a small integer (31 bits)
               // xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx10 -> a constant index (30 bits)
               // xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx00 -> reference in heap (32 bits aligned)
             

   Il faut donc mettre à jour le fichier Values.java.
   De plus, expliquer pourquoi à la question précédente, le heap est déclaré comme un ByteBuffer et pas comme un IntBuffer ?

Exercice 2 - Création d'objet, initialisation et accès aux champs

         Point = { x, y }
         p = Point(1, 2)
         p
       

         Empty = {}
         Empty()
       

         LDC $Empty$
         NEW_INSTANCE
         RET
       

1. Ecrire dans le StackInterpreter le code corrspondant à NEW_INSTANCE sachant que NEW_INSTANCE doit réserver sur le tas (heap), l'espace nécessaire pour pouvoir staocker la classe de l'instance ainsi que l'ensemble des champs de la classe.
2. Ecrire dans le Rewriter le code correspondant au noeud de l'AST Struct sachant que on va pour l'instant se limiter au cas où il n'existe pas de champs. Le code du constructeur est donc

              LDC $classe_courante$
              NEW_INSTANCE
              RET
            

   
   Attention, le constructeur étant une fonction, son code doit être générer après le code du script courant (de la même façon que le code d'une lambda est générée après le code du script courant). Il vous faudra donc changer un peu la façon dont de Rewriter ré-écrit les fonctions dans le cas où la fonction est une classe.
3. On s'intéresse maintenant aux classes qui peuvent avoir des champs, dans ce cas, le constructeur va prendre en paramètre les valeurs des champs et il va falloir initialiser ceux-ci.
   Pour initiliser un champs, on utilisera l'instruction FIELD_PUT qui pré-supposera que la pile contient une instance de la classe dont on veux changer la valeur du champ et une valeur et initialisera le champs (dont le nom est passé en argument de l'opcode FIELD_PUT dans le code).
   Ecrire le code de l'instruction FIELD_PUT dans la classe StackInterpreter.
4. Modifier dans le Rewriter le code qui génére le constructeur d'une classe pour qu'il soit possible de créer des classes ayant des champs. Le constructeur devra être une fonction qui prend en paramètre autant de paramètres qu'il y a de champs et qui utilisera la valeur de chaque paramètre pour initilialiser chaque champs.
   Par exemple, pour le code Talk suivant:

              Pixel = { color }
              pixel = Pixel(3)
            

   Le code du constructeur devra être:

              LDC $classe_courante$
              NEW_INSTANCE
              DUP                // on charge l'instance courante
              VAR_LOAD 0         // on charge le premier paramètre
              FIELD_PUT color    // on modifie le champ color
              RET                // on renvoie l'instance
            

5. Ecrire dans le Rewriter le code correspondant au noeud de l'AST FieldAccess.
6. Ecrire dans l'interpreteur le code correspondant à l'instruction FIELD_GET.
   Tester avec le code Talk ci dessous:

              v = { x }(3)
              fun = |self| [ @x ]
              fun(v)
            

   Note: la syntax '@x' est hérité de Ruby et veut dire prendre la champ 'x' du premier paramètre de la fonction, c'est l'équivalent de self.x en Java.

Exercice 3 - Association de méthodes et appel de méthodes

          Foo = { v }
          foo1 = Foo(3)
          fun = |this| [ @v ]
          foo1.bar = fun   // la function fun est lié à la classe Foo sous le nom bar
          foo1.bar()       // 3
          foo2 = Foo(4)
          foo2.bar()       // 4
        

1. Ecrire dans le Rewriter le code de l'assignation de méthode (MethodAssignment).
2. Ecrire dans l'interpreteur le code correspondant à l'instruction METHOD_PUT.
3. Comme pour un FIELD_STORE le résultat d'une foo.bar = baz doit être la valeur de baz.
   Tester que le code suivant fonctionne:

               v = { x } (7)
               fun = |zorg| [ @x ]
               (v.zap = fun)(v)  // 7
             

4. On souhaite maintenant implanter l'appel de méthode

               v.zap()
             

   En fait, celui-ci peut être décomposé en deux instructions, la première METHOD_GET consiste à récupérer la fonction dans la classe de l'instance en sommet de pile puis l'instruction APPLY qui va faire l'appel de la fonction classique.
   Comme une méthode est une fonction dont le premier paramètre est l'instance sur laquelle on fait l'appel de fonction, il faut aussi dupliquer l'instance car celle-ci est utiliser et par METHOD_GET et par APPLY.
   Le code d'appel de la méthode ci-dessus, doit donc être traduis par

               DUP               // on duplique l'instance sur la pile
               METHOD_GET zap    // on consomme une instance et on recoit une fonction
               SWAP              // on echange la fonction et l'instance sur la pile
               APPLY             // on appel la fonction avec l'instance en paramètre
             

   
   Ecrire le code dans le Rewriter pour l'appel de méthode.
   Attention aux arguments de l'appel de méthode !
5. Ecrire le code pour exécuter l'instruction METHOD_GET dans l'interpreteur.

Exercice 4 - Garbage Collection (Préparation)

1. Ecrire le test permettant de déclencher le garbage collector dans l'interpreteur en appelant une méthode doGC.
2. Dans le but de pouvoir marquer tous les objets vivants, ecrire dans doGC un code permettant de parcourir les valeurs sur la pile et de détecter celles qui sont des références vers le tas.
3. Comme on souhaite marquer tous les objets vivants, il faut réserver dans chaque objet une place, un emplacement supplémentaire, pour pouvoir marquer les objets. Comme on utilisera cette place lors de la suite de l'algorithme, on va réserver 32 bits et on marquera les objets avec la valeur -1.
   Pour un accès facile, on mettra la marque à la place du premier champs de l'objet (celui à l'offset 0).
   Modifier la classe Klass pour que la taille d'un objet prennent en compte cet emplacement supplémentaire.
4. Modifier le code pour marquer tous les objets vivants récursivement.
   Attention aux cycles !
5. Ecrire un code de parcours du heap du bas vers le haut affichant si les objets sont mort ou vivants, c-a-d s'ils ont été marqué ou non.
6. Modifier le code du parcours du heap pour calculer l'adresse que devront avoir les objets (vivant) après compaction et stocker cette adresse dans l'emplacement supplémentaire.
7. On peut remarquer que Talk ne permet de créer que des objets non mutables, c-a-d des objets dont les champs ne changent jamais de valeur. Donc par construction, les références contenuent dans les champs pointent toujours vers des adresses plus bas dans le tas.
   Il est donc possible de modifier le référence des champs d'un objet lors du parcours du tas car on connait déjà la nouvelle adresse.
   Modifier le code de parcours du heap pour changer les valeurs des champs si ceux-ci sont une référence.
8. Une fois que chaque objet connait sa future adresse dans la tas, il est possible de ré-écrire les références sur la pile pour les faire pointer vers la nouvelle adresse.
   Ajouter un code qui parcours la pile pour mettre à jour toutes les références.
9. Enfin, écrire le code qui parcours les objets du tas et qui bouge les objets vivants à leur nouvelle adresse.
10. Tester votre algo de GC :)
    Vous pouvez utiliser pour cela le programme suivant:

               alloc = [ {a, b, c}(1, 2, 3) ]
               alloc()
               alloc()
               alloc() 
             

    Avec un tas de 20 octets.