Projects

Chaque étudiant doit choisir son projet parmis ceux proposés. Un seul projet par personne et une seule personne par projet.
Les projets sont classés en 3 catégories, facile, notés sur un maximum de 12, assez facile avec un maximum à 16 et moins facile avec un maxium à 20.
Les projets sont à réaliser en modifiant soir l'interpreteur du lab2 soit l'interpreteur du lab3.

Les projets doivent être rendu avant le jeudi 27 mars 2013 à 23h59 sous forme d'un fichier ZIP (pas RAR ou autre) sur la platforme d'e-learning.
Le ZIP doit contenir le code source répondant au sujet, un exemple de plusieurs code Talk permettant de montrer que votre code répond bien au problème poser plus un rapport au format PDF de 15 pages minimum en police 11 (sans le code) indiquant

• Une re-formulation du problème posé en 1 page.
• La démarche que vous avez utiliser pour résoudre le problème.
• Les différentes pistes que vous avez explorées (même celles ne nenant nulle part), et les avantages/inconvénient de chaque piste.
• Le ou les algorithmes que vous avez mis en place. En décrivant ceux-ci et en terme généraux et en pseudo-code.
• Et enfin, une section expliquant les différentes parties de votre code, relié aux algorithmes que vous avez implantés et les différents bugs qui n'ont pas été corrigé.
• Il vous est de plus demander, un sommaire, une introduction, une conclusion, ainsi qu'une liste des articles (et ou URL) que vous avez lu pour résoudre le projet.

Le but de ce projet est de porter le langage Talk en JavaScript.
L'idée consiste au lieu de générer directement du JavaScript (ce qui n'est pas facile vu la sémantique de Javascript) à générer du bitcode LLVM [1] sous forme textuelle à partir du langage Small puis d'utiliser Emscripten [2] pour transformer le bitcode LLVM en Javascript.
Comme LLVM n'offre pas de support pour les langages dynamiques, il vous est demandé de porter uniquement la partie fonctionnel du langage Small, pas les objets, pas les méthodes, pas le GC, mais uniquement les fonctions, les operations, etc.
[1] http://www.llvm.org/
[2] https://github.com/kripken/emscripten

Le but de ce projet est de porter le langage Talk en C.
L'idée consiste à générer du code C à partir du langage Talk, le code généré sera ensuite compilé par GCC dans le but de créer un exécutable.
Talk étant un langage qui a des constructions dynamiques, l'accès aux champs, l'appel de méthode, etc. il faudra écrire une bibliothèque de support en C implantant les différents algorithmes dont le code C généré aura besoin.
Dans le but de simplifier l'allocation, on ne vous demande pas ici d'implanter un algorithme de GC mais d'utiliser malloc pour faire l'allocation dynamique sans free.
[1] http://gcc.gnu.org/

Le but de ce projet est de modifier le GC implanté lors du lab2 pour que de marquage soit façon de façon concurrente [1] avec l'exécution du programme. La phase d'évacuation reste elle effectuer alors que le programme est arréter.
Lors du démarrage de l'interpreteur, celui-ci lance un thread qui servira au marquage. Par défaut ce thread est en attente. Lorsque le tas arrive à 75% d'occupation, le thread effectue le marquage des objets et tout objet nouvellement crée est considérer comme marqué.
Lorsque le GC se déclenche, il attend la fin du marquage par la thread de marquage si nécessaire et bouge les objets en mémoire.
J'attire votre attention sur le faite que comme il y aura deux threads dans votre interpreteur, la concurrence devra être gérer correctement. Si l'interpreteur que vous produisez n'est pas thread safe, je considèrerais que le projet n'est pas valide.
[1] https://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29

Le but de ce projet est d'implanter l'optimisation tail-call dans l'interpreteur de Talk.
Il faut dans un premier temps, reconnaitre les méthodes ayant une récursivité terminal et donc succeptible d'être optimisé, puis dans un second temps, implanter l'optimisation [1][2] tail-call.
[1] https://en.wikipedia.org/wiki/Tail_call
[2] http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/

Le but de ce projet est d'implanter un algorithme d'escape analysis [1][2] permettant de savoir quel sont les objets qui peuvent être allouer sur la pile au lieu d'être allouer dans le tas.
Le but ce ce projet est juste de sortir une liste de tous les sites allocation d'objet qui sont succeptibles d'être optimisé et non d'effectuer l'optimisation en elle même.
[1] https://en.wikipedia.org/wiki/Escape_analysis
[2] https://dl.acm.org/citation.cfm?id=320386

Le but est de modifier le code de l'interpreteur pour que le calcul du maxStack et maxLocals [1] soit fait lors de l'étape de génération en utilisant un algorithme linéaire plutôt que en laissant la bibliothèque ASM faire la travail avec un algorithme en temps exponentiel.
[1] http://download.forge.objectweb.org/asm/asm4-guide.pdf

Le but est de modifier la façon dont l'interpreteur accède aux champs des objets.
Actuellement, l'interpreteur génère une serie de GuardWithTest dont l'ordre dépend de l'ordre dans lequel les classes du receveur ont été vu pour la première fois.
L'idée de ce projet consiste à monitorer le nombre de fois que chaque branche des GuardWithTest est utilisée puis lorsque le nombre d'accès total pour une instruction d'accès au champ dépasse 999 de ré-ordonner les GuardWithTest en fonction de leur fréquence d'utilisation (le plus fréquent en premier).

L'accès à un champ en Talk se fait par son nom, il est donc possible de savoir si un champ est utilisé par un script Talk où pas, ce n'est ps complètement vrai car deux structures peuvent avoir des champs de même nom mais si le nom d'un champs n'apparait pas pour tous les accès, alors le champ n'est pas utilisé.
L'idée de cette optization consiste à parcourir l'AST complet d'un script et d'enregistrer l'ensemble des noms de tous les champs qui peuvent être accéder. Puis lors de la génération de code d'une classe de supprimer le stockage de valeur pour les champs non accédés.
Par exemple, avec le script suivant

          A = { x, y }
          a = A(1, 2)
          B = { x }
          b = B(3)
          fun = |self| [ @x ]
          a.fun = fun
          a.fun()
        

Le champ y de A ne devra pas être créer, le champs x de B n'est pas accéder mais l'analyze ne nous permet pas de le dire.

Actuellement le générateur de bytecode de l'interpreteur est assez basique, par exemple pour l'expression x + 1, le code générer est le suivant

          aload 0
          invokedynamic "1" ()Ljava/lang/Object; bsm_const 1
          invokedynamic "ADD" (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object; bsm_binary
        

Donc, 1 est boxé en un Integer pour ensuite être unboxé pour effectuer l'opération +.
Le but de ce projet est de modifier le générateur de code pour opérations unaires et binaires dans le cas où un des paramètres est une constante pour que les opérations unaire et binaire puisse prendre des types ptimitif (int en fait) en paramètre.
Dans l'exemple, le code suivant devra être générer

         aload 0
         ldc 1
         invokedynamic "ADD" (Ljava/lang/Object;I)Ljava/lang/Object; bsm_binary
       

L'implantation consiste à implanter un nouveau visiteur qui va parcourir l'AST avant la génération de code et assigné pour chaque noeud un type (ici: OBJECT ou INT) puis lors de la génération d'utiliser l'information de type dans le cas où l'opération est unaire ou binaire pour générer la signature de l'instruction invokedynamic.

La grammaire actuelle du langage Talk ne définie pas les opérations booléens paresseux classique que sont le && et le ||.
Le but de ce projet est de modifier la grammaire de Talk pour supporter ces deux opérateurs puis d'implanter les deux opérations lors de la génération de code.
Attention, && et le || ne doivent pas évaluer [1] la partie droite dans le cas ou la partie gauche permet de calculer le résultat sans évaluer la partie droite.
[1] https://en.wikipedia.org/wiki/Short-circuit_evaluation

L'idée de ce projet est de permettre à un utilisateur d'ajouter des informations de type au langage small. Tous les variables locales et paramètre dont le nom commence par '$', devra être considérer lors de l'exécution comme un entier.
L'idée ici, n'est pas d'utiliser les informations de type pour optimizer la génération du code mais pour vérifier que les fonctions et les variables contiennent des valeurs correctes.
Si une variable ou un paramètre est assigné avec une valeur qui n'est pas du bon type, le programme devra s'arrêter avec un message d'erreur.
Par exemple,

          fun = |$x| [$x]
          fun(3)     // ok
          fun(fun)   // plante en inindiant que $x n'est pas un entier mais une fonction. 
        

Le projet consiste donc à modifier la grammaire de Talk pour supporter les identifiant commençant par '$' puis à modifier la génération de code pour insérer une vérification si les variables ont un nom qui commence par un '$'

La grammaire actuelle du langage Talk ne définie pas de façon de faire des boucles, on souhaite pour cela ajouter la syntaxe expr1 .. expr2 expr3 qui va exécuter l'expression expr3 pour les valeurs entre [ expr1 et expr2] (croissant ou décroissant).
l'accès à la valeur à l'intérieur de expr3 se fera grâce à une variable dont le nom est it.
Par exemple le code suivant, devra appeler la fonction fun avec les valeurs de 0 à 9 (compris).

          fun = |x| []
          0 .. 9 fun(it) 
        

qui affiche les nombres de 0 à 9.

Pour cela, il vous faut modifier la grammaire du langage Talk et modifier le générateur de code pour transformer la syntaxe range en l'équivalent d'une boucle while [1].
[1] https://en.wikipedia.org/wiki/While_loop

Le but de ce projet consiste implanter un algorithme simple d'allocation de registre. Actuellement, lors de la génération, chaque nouvelle variable utilise un nouveau slot même si une variable locale n'est plus utilisé.
On vous demande d'utiliser les informations de liveness [1] pour réutiliser l'emplacement (les slots) des variables locales [2] lors de la génération.
[1] https://en.wikipedia.org/wiki/Liveness_analysis [2] https://en.wikipedia.org/wiki/Register_allocator

Le but de ce projet est d'implanter un algorithme calculant si une fonction du langage Talk est pure ou non, une fonction pure est une fonction qui ne fait pas d'effet de bord ou qui n'est pas succeptible de faire des effets de bord.
Le langage Talk possède une seul construction qui est succeptible de faire des effets de bord, l'assignation d'une fonction comme méthode d'un objet.
Par exemple, la fonction suivant n'est pas pure.

          fun = |c, f| [ c.m = f ]
        

Comme le language Talk permet aussi de faire des appels de méthodes, et qu'un appel de méthode va appeler une fonction inconnue, la fonction suivante est aussi pas pure.

          fun = |i| [ i.m() ]
        

Le but est donc d'afficher à partir d'un script Talk, pour chaque fonction, la ligne qui déclare la fonction ainsi que si celle-ci est pure ou non.

Le but de ce projet est de modifier l'appel de fonction pour incrémenter un compteur par fonction indiquant le nombre de fois qu'une fonction a été appelé puis lors de la fin d'exécution du programme d'afficher pour chaque fonction, la ligne où celle-ci a été déclaré ainsi que le nombre de fois où la fonction a été appelée.
L'affichage devra se faire dans l'ordre décroissant du nombre d'appel (donc la fonction la plus appelée d'abord.
Attention, les constructeurs des objets sont aussi des fonctions et donc ils doivent aussi posséder un compteur.

La propagation des constantes ou constant folding [1] en anglais, consiste a éviter de faire des calculs à l'exécution si ceux-ci peuvent être simplifier lors de la génération du code.
En Talk, dans le cas des opérations unaire et binaire, il est possible d'optimizer le code générer pour effectuer le calcul des constantes lors de la generation plutôt qu'à l'exécution.
par exemple le code Talk:

         fun = |x| [x]
         fun(2 + 3)
        

devra lors de la génération en bytecode être équivalent au code suivant

         fun = |x| [x]
         fun(5)
        

En terme d'inplantation le plus simple est de ré-écrire l'AST pour simplifier les constantes juste avant la génération.
[1] https://en.wikipedia.org/wiki/Constant_folding