TER de Master Recherche (M1) en Informatique ou Math-Info --- 2007-2008
Hiérarchies aléatoires de classes et hachage parfait.

Encadrants : Roland Ducournau, Anne-Elizabeth Baert

email : Roland.Ducournau at lirmm.fr

Lieu : LIRMM/INFO/DOC, Montpellier

Ce sujet de TER est destiné à des étudiants de Master 1 Informatique ou Math-Info

Contexte : Implémentation efficace des langages à objets.

Ce travail s'insère dans le contexte général de l'étude théorique et expérimentale de l'implémentation des langages à objets.
Si elles débouchent, les techniques mises au point seront intégrées dans le compilateur du langage PRM développé par Jean Privat dans le cadre de sa thèse, pour tester un nouveau schéma de compilation et spécifier diverses fonctionnalités nouvelles. Ce stage fait suite à plusieurs stages de DEA/M2R portant sur l'implémentation des objets. Au cours du précédent, Floréal Morandat, actuellement en thèse, a développé un compilateur autogène (de PRM en PRM).

Objectif du projet

Dans un travail antérieur à paraître [Ducournau 2005], nous avons proposé d'appliquer le hachage parfait [Sprugnoli 1977, Czech et al 1997] au test de sous-typage dans les hiérarchies de classes en héritage multiple, dans un contexte de chargement dynamique. Dans le cas de JAVA et des autres langages en héritage simple de classes mais avec sous-typage multiple d'interfaces, la technique s'applique au test de sous-typage lorsque le type cible est une interface mais aussi à l'invocation de méthodes lorsque le receveur est typé par une interface.
Une variante, la numérotation parfaite, consiste à  générer les identifiants de classes de façon à optimiser la taille des tables de hachage résultantes.

Les deux techniques ont été testées par des simulations sur de très grandes hiérarchies de classes, avec des résultats intéressants mais sans doute perfectibles.
Si les hiérarchies de classes utilisées comme benchmarks sont des hiérarchies "réelles", l'ordre de chargement des classes considéré est resté arbitraire et l'effet de ses variations n'a pas été étudié. Or la simulation de la numération parfaite a montré que le résultat était fortement dépendant de l'identifiant arbitraire donné à la racine de la hiérarchie. Il est donc probable que l'ordre du chargement a une influence non négligeable sur la qualité du résultat (càd la taille des tables produites).
Il est apparu aussi que les résultats sont globalement très bons sur la totalité des benchmarks, sauf 1, et assez médiocres sur cette unique exception.

Aussi, l'objectif de ce projet est de s'affranchir de ces hiérarchies réelles et de cet ordre de chargement arbitraire, pour faire une étude plus abstraite, basée sur des résultats théoriques, des modèles aléatoires et des simulations statistiques. De façon non limitative, on peut déjà lister les problèmes suivants :
  1. Une hiérarchie de classes étant donnée, proposer un modèle aléatoire réaliste de distribution des ordres de chargement dynamique.
    Faire les simulations basées sur ce modèle et les hiérarchies réelles.
    Tout résultat théorique serait un plus.
  2. Faire une analyse statistique de la structure des hiérarchies réelles et en déduire un modèle réaliste de distribution des hiérarchies de classes.
    Faire les simulations basées sur la génération automatique de hiérarchies respectant ce modèle de distribution et le modèle de chargement de la question 1.
    Tout résultat théorique serait un plus.
  3. Etude théorique et variantes du hachage parfait appliqué aux hiérarchies de classes.
    En particulier, étudier d'autres fonctions de hachage que les 2 déjà envisagées (modulo et & binaire).
  4. Etude théorique et variantes de la numération parfaite des hiérarchies de classes.
    Parmi les variantes à considérer, le problème de la numérotation parfaite peut être généralisé à la numérotation optimale d'un ensemble de classes chargées en même temps --- en effet le chargement d'une classe peut conduire à charger un certain nombre de super-classes non encore chargées.
NB1. Deux contextes légèrement différents sont à envisager : l'héritage multiple (comme en C++ ou CLOS) ou le sous-typage multiple (comme en JAVA ou C#).

NB2. La littérature sur le hachage est très vaste. Le comportement statistique des différentes techniques repose en général sur l'analyse du comportement d'une table de hachage isolée face à un flot de valeurs à hacher qui suit une certaine distribution.
Le hachage parfait change un peu ce point de vue, puique cette technique de hachage sans collision ne s'applique qu'aux tables constantes et que l'absence de collision entraîne un comportement temporel parfaitement uniforme  :  c'est le comportement spatial (la taille des tables)  qui est le but de l'évaluation.
L'application du hachage parfait à l'implémentation des hiérarchies de classes change encore le point de vue : il ne s'agit pas d'une table de hachage isolée, mais d'un ensemble cohérent de tables de hachage --- une par classe --- dont il s'agit d'évaluer la taille totale. La présence du pire des cas n'est pas un problème si ce pire des cas est compensé par suffisamment de bons cas pour que le total soit bon.
Enfin, la numérotation parfaite est un nouveau changement de perspective et inverse partiellement le problème. Au lieu de partir d'un schéma convenu de numérotation des classes, suivant l'ordre du chargement, il s'agit de trouver le schéma de numérotation, forcément glouton, dont on s'attend à ce qu'il optimise la taille totale des tables.

Compétences requises

Bases en programmation par objets, pour le contexte.
Bases en probabilités-statistiques.
Bonnes compétences en mathématiques discrètes, algorithmique (graphes, ordres) et programmation.
Des compétences plus pointues en génération de graphes aléatoires seraient idéales, de même que de bonnes connaissances sur les techniques de hachage.
Le stage peut être tiré sur le versant théorique et probabiliste ou au contraire sur le versant pratique et statistique, suivant les compétences et les goûts du stagiaire.
Pour les simulations, une plate-forme de test en Common Lisp existe, mais les tests sont suffisamment simples pour pouvoir être faits à partir de rien.

Bibliographie

Celle de l'équipe :
  1. R. Ducournau.
    Perfect hashing as an almost perfect subtype test.
    Rapport de Recherche 05-058, L.I.R.M.M., Montpellier, 2005 (soumis à ACM TOPLAS 2005, révisé 2006). (pdf file)

  2. J. Privat and R. Ducournau.
    Link-time Static Analysis for Efficient Separate Compilation of Object-Oriented  Languages
    In ACM  SIGPLAN-SIGSOFT  Workshop on Program Analysis for Software Tools and Engineering (PASTE'05), pages , 2005

  3. R. Ducournau.
    Implementing statically typed object-oriented programming languages.
    Rapport de Recherche 02-174, L.I.R.M.M., Montpellier, 2002/2005. 

  4. J. Privat.
    De l'expressivité à l'efficacité une approche modulaire des langages à objets. Le langage PRM et le compilateur prmc (voir le site de Jean Privat)
    Thèse d'Informatique. Université Montpellier II, juillet 2006.
Il faut y ajouter tout ce qui concerne le hachage parfait :
  1. R. Sprugnoli
    Perfect hashing functions: a single probe retrieving method for static sets,
    Comm. ACM, 20(11) , 1977, 841--850.
  2. Zbigniew J. Czech and George Havas and Bohdan S. Majewski
     Perfect hashing,  Theor. Comput. Sci. 182 (1-2), 1997, 1--143