Stage au JAIST — Année 2015-2016 — Nomi (Ishikawa)
Contexte
Lorsque l'on pense aux optimisations qu'un compilateur fait, on pense rapidement à des optimisations comme le calcul et la propagation des constantes, la prédiction des branchements conditionnels ou encore au réagencement de l'odre des opérations d'un calcul pour tirer partie au mieux des instructions offertes par un certain type de CPU.
Ici, on s'intéresse non pas à des optimisations bas niveau mais à identifier des algorithmes classiques connus pour être peu efficaces en temps (eg. le tri à bulles) ou en mémoire (eg. la version récursive naïve de la suite de Fibonacci).
Pour ce faire, on écrit des templates suffisament génériques pour quelles puissent reconnaitrent un algorithme spécifique. Ces templates font apparaitre des symboles
Lorsque l’on compile des programmes on aimerait pouvoir reconnaitre des algorithmes peu efficaces et les remplacer par des variantes plus performantes. On peut faire cela avec une sorte de pattern matching qui reconnait un algorithme et le remplace par un autre. Cependant pour appliquer cette transformation il faut que l’on soit capable de vérifier certaines propriétés sur les fonctions qui apparaissent dans le programme original. Le problème majeur survient quand les fonctions sur lesquelles on veut dériver ces propriétés présentent une propriété de commutativité. En effet, la commutativité est très dure à gérer correctement dans le modèle que l’on a utilisé et qui était fondé sur des systèmes de réécritures.
Présentation du Stage
J'ai effectué ce stage au JAIST (Japan Advanced Institute of Science and Technology) sous la supervision de Nao Hirokawa et Yuki Chiba au cours de l'année académique 2015-2016.
L'objectif de ce stage était d'étendre le framework RAPT, un framework de réécriture à base de templates. Cependant, pour appliquer une template il faut vérifier certaines conditions sur les sous-fonctions apparaissant dans la template. Mon stage avait pour but de trouver un moyen de vérifier automatiquement ces propriétés.