Comptes rendus de travaux aux sein de Tralala

Les Crawlers dans CDuce.

Date : du 17/03/06 au 21/03/06.
Lieu : Marseille.
Collaborateurs :

• Lucia Acciai
• Silvano Dal Zilio
• Kim Nguyễn

La base du travail est l'algèbre de filtres/patterns/crawlers avec accumulateurs proposés par Silvano et Lucia (et présentés à la réunion Tralala du 26 Janvier 2006). Un prototype existant consiste en un traducteur des filtres en fonctions récursives CDuce, dont le type est calculé par un algorithme d'approximation.En effet, la sémantique d'un crawler est de renvoyer ses accumulateurs, mais ces derniers peuvent contenir des valeurs dont le type le plus précis sort de la classe des langages réguliers d'arbres. Le problème avec cette aproche est que même si une approximation peut être trouvée pourle type final des accumulateurs, le type de ceux-ci au cours de l'évaluation de la fonction peut varier. Or, les références sont typées en CDuce. On se retrouve donc forcé d'avoir des références de contenu Any (pour pouvoir mettre ce qu'on veut dedans...) et de refaire un typecase final (à runtime) alors qu'on sait que la valeur finale est du type calculé.

Le travail inité pendant cette semaine consiste à rajouter les crawlers comme un nouvel objet du langage CDuce et d'intégrer directement l'algorithme de typage. Les crawlers ne sont plus réprésentés comme des fonctions récursives, mais comme des automates (munis de piles) en interne.

Le principal problème est de faire cohabiter l'algorithme d'approximation (basé sur des listes plates à la XDuce) avec l'algèbre de type de CDuce (produits imbriqués), afin de pouvoir réutiliser le mécanisme interne de CDuce pour résoudre les équations de typage. D'autres problèmes plus mineurs sont liés à l'intégration de ces automates au runtime de CDuce et leur cohabitation avec l'algèbre de patterns existante (d'une implémentation complexe, notement à cause des nombreuses optimisations).