Qui ne connaît pas XML ? Les esprits chagrins nous disent qu'il ne s'agit que d'une syntaxe pour faire tenir des arbres dans des fichiers textes, et ils ont raison. Mais un arbre, ça peut être n'importe quoi, et deux applications qui veulent communiquer grâce à XML doivent bien se mettre d'accord sur le type des documents échangés. Un type restreint plus ou moins la structure arborescente, les étiquettes, les valeurs atomiques, le texte,... que l'on trouve dans les documents.
Il est assez naturel de prendre en compte ces types dans un langage de programmation adapté à XML. L'objectif est, entre autres, de garantir statiquement qu'une application à qui l'on donne un document du bon type XML ne va pas produire des documents d'un mauvais type. Je présenterai très rapidemment le langage CDuce, développé au sein de l'équipe Langages du DI, qui s'inscrit dans cette perspective.
La théorie sous-jacente aux types XML est celle des automates d'arbre, qui généralise celle bien connue des automates de mots. Une deuxième partie de l'exposé introduira cette théorie. Malheureusement, la compilation de CDuce pose des problèmes mal résolus par les automates d'arbre classiques. Dans une troisième partie, je présenterai mes travaux en cours, sur une variante "non-uniforme" des automates déterministes, qui gardent la même puissance expressive mais sont bien plus efficaces.
L'exposé consistera en un mini-cours au tableau; aucune connaissance préalable ne sera nécessaire pour le suivre.