Projects

Chaque étudiant doit choisir son projet parmis ceux proposés. Un seul projet par personne et une seule personne par projet.

Les projets doivent être rendu avant le dimanche 29 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, des exemples (une 20aines) de code Script 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 demandé, 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 Script en JavaScript.
L'idée est de reprendre l'interpreteur vu au Lab 1 et de proter celui-ci en JavaScript pour donc interpreter le language script en JavaScript.
Il faut pour cela écrire un perseur en JavaScript permettant de parser le langage Script et de créer l'AST correspondant (vu utiliser pour cela la bibilothèque de votre choix). Puis ecrire un interpreteur de l'AST.

Le but de ce projet est d'implanter l'optimisation tail-call dans l'interpreteur de Script.
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 de record 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 d'implanter l'algorithm [2] permettant de refactoriser les expressions communes du langage Script en utilisant la technique de 'Common sub-expression removal' [1].
Cette technique sera implanter sous forme d'un visiteur qui prendra l'AST en paramètre et générera une nouvelle AST mettant en commum les expressions similaires.
[1] https://en.wikipedia.org/wiki/Common_subexpression_elimination
[2] http://dl.acm.org/citation.cfm?id=390013.808480

La grammaire actuelle du langage Script 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 Script 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

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ée.
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.
Vous devrez pour cela modifier le générateur de bytecode du Lab 3.
[1] https://en.wikipedia.org/wiki/Liveness_analysis [2] https://en.wikipedia.org/wiki/Register_allocator

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 Script, 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 Script suivant :

         fn(main:
           print(2 + 3)
         )
        

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

         fn(main:
           print(5)
         )
        

En terme d'inplantation, il vous ait demander de créer un visiteur intermédiaire qui prend en paramètre un AST et génére un nouvelle AST ayant aggloméré les constantes.
[1] https://en.wikipedia.org/wiki/Constant_folding