Vincent Balat

Sujet

Le but de ce stage est d'explorer une application assez inattendue de l'algorithme de normalisation par évaluation : la génération de Javascript depuis un programme OCaml.

Normalisation par évaluation, décompilation par évaluation

La Normalisation par Évaluation (NBE) est généralement vue comme une technique permettant d'obtenir la forme normale d'un lambda-terme en extrayant un représentant canonique de son interprétation dans un modèle dénotationnel. Mais cette technique peut être implémentée concrètement et a déjà été utilisée pour faire de l'évaluation partielle de programmes (c'est-à-dire créer des versions spécialisées de programmes). C'est ce que l'on appelle l'Évaluation Partielle Dirigée par les Types (TDPE). Dans cette utilisation, un algorithme de quelques lignes seulement permet de générer un code source en forme normale à partir d'un programme compilé ! L'outil de normalisation par évaluation a donc la propriété (assez magique !) de décompiler les programmes. Alors que l'on peut l'implémenter sans rien connaître du langage machine ou du bytecode...

Application à la programmation d'applications Web distribuées

Nous souhaitons exploiter ces propriétés de décompilation afin de générer du code à exécuter dans un navigateur, dans le cadre d'une application Web distribuée. Le but est de construire des applications client-serveur avec interface Web. Sur le serveur Web tourne une application qui génère des pages dans lesquelles sont inclus des exécutables (par exemple du Javascript). Nous souhaitons programmer les deux côtés de l'application dans un seul langage (OCaml) et comme une seule application. Pour l'instant le module Eliom d'Ocsigen génère statiquement les portions de code à exécuter dans le navigateur (en utilisant un compilateur vers Javascript). L'alternative que nous souhaitons explorer est la génération dynamique de code spécialisé pour le client. Et plutôt qu'embarquer le compilateur OCaml dans le serveur Web, nous souhaitons voir s'il est possible de faire de la décompilation vers Javascript par évaluation. Cela devrait permettre en théorie d'envoyer sur le client des fonctions dont on ne dispose pas du code (par exemple des fonctions de bibliothèques déjà compilées).

Difficultés et enjeux

L'application de la normalisation par évaluation à un cas aussi concret pose de nombreux problèmes :

• La normalisation par évaluation est un algorithme prévu pour des programmes fonctionnels purs. Il nous faudra donc inventer des techniques pour que les effets de bord n'aient pas lieu pendant la normalisation mais soient intégrés au programme cible. Il faut réussir à contrôler la normalisation pour que les effets aient lieu au bon moment.
• Le programme client devra pouvoir accéder à une partie des bibliothèques OCaml mais aussi à des interface propres au navigateur. Il faudra un moyen de préciser ce que l'on souhaite inclure ou non dans le programme final.
• NBE s'implémente très facilement lorsque l'on se limite aux types flèche et produit mais il en est tout autrement lorsque l'on ajoute les types sommes. Plusieurs solutions ont déjà été proposées mais elles ne sont pas forcément simple à mettre en œuvre dans notre cas (à cause par exemple de l'utilisation d'opérateurs de contrôle).
• NBE produit des lambda-termes qu'il va falloir ensuite traduire en Javascript, en prenant en compte les spécificités de ce langage. Il faudrait aussi réfléchir à une façon simple d'appeler des méthodes Javascript.

Tous ces problèmes rendent très difficile l'utilisation de TDPE dans des cas réels. Mais nous espérons que certaines solutions soient envisageables dans ce cadre précis et permettent de progresser dans la recherche sur cette technique de normalisation.

Enfin nous nous pencherons sur l'intégration à Eliom de techniques de génération dynamique de code.

Le stage devrait déboucher sur l'écriture d'un prototype.

Références

• Eliom
• TDPE : http://portal.acm.org/citation.cfm?id=237784, http://www.brics.dk/~danvy/tdpe-ln.pdf, http://www.pps.jussieu.fr/~balat/publications/these-balat.pdf