Le prix de thèse Gilles Khan attribué à Raphaëlle Crubillé

Raphaëlle Crubillé obtient le prix Gilles Khan de la Société informatique de France (SIF), pour sa thèse « Distances comportementales pour des programmes probabilistes d’ordre supérieur »1 . Soutenue le 20 juin 2019, elle a été dirigée par Thomas Ehrhard, directeur de recherche CNRS à l’Institut de recherche en informatique fondamentale (IRIF, CNRS/Université Paris Diderot), et Ugo Dal Lago, professeur à l’université de Bologne.

« Les programmes d’ordre supérieur utilisent des fonctions, en entrée et/ou en sortie, au lieu de nombres entiers ou d’une information binaire vraie/faux, explique Raphaëlle Crubillé. Ils sont plus facilement modulables, car les fonctions permettent de réemployer certaines parties du code, plutôt que de les recopier. Cela limite les risques d’erreurs. »

Dans leurs versions probabilistes, ces algorithmes tirent au hasard quelle branche de leur code exécuter. Un principe qui a trouvé ses premières applications dans le monde de la cryptographie. Le hasard complique énormément le travail d’un adversaire qui voudrait comprendre comment casser un code en répétant plusieurs fois une même manœuvre, qui donnera du coup des résultats différents à chaque fois.

Les programmes probabilistes servent également à construire des modèles physiques, par exemple pour le climat. « Quand on ne possède pas toutes les informations ou qu’elles sont trop lourdes pour être manipulées, une distribution probabiliste peut se rapprocher suffisamment de la réalité, détaille Raphaëlle Crubillé. On retrouve aussi cela au cœur du machine learning, qui apprend en calculant quelle est la solution la plus probable. »

C’est son intérêt pour l’alliance de l’analyse des probabilités et des outils informatiques qui ont mené Raphaëlle Crubillé sur la voie de cette thèse, après un stage de master auprès d’Ugo Dal Lago. « Avec des usages tels que le machine learning, les programmes probabilistes sont très à la mode, souligne-t-elle. Mais l’étude de langages de programmation qui soient à la fois fonctionnels et probabilistes en est encore à ses débuts. Cela m’intéressait beaucoup de voir comment on pouvait garantir formellement des spécifications sur de tels programmes. »

• 1Behavioral distances for probabilistic higher-order programs

La chercheuse s’est placée dans un cadre assez abstrait et théorique, s’intéressant ainsi aux concepts d’équivalence et de distance comportementale. Il s’agit de mesurer et vérifier si deux programmes donnent bien le même résultat, ce qui est plus compliqué quand ils sont de nature probabiliste. Il faut donc déterminer jusqu’à quelle marge d’erreur on peut les considérer comme suffisamment proches, ou non.

Raphaëlle Crubillé combine une approche opérationnelle, qui regarde comment les programmes s’exécutent, et une approche dénotationnelle, où ils sont manipulés comme de purs objets mathématiques. Dans sa thèse, elle utilise les nombreux outils disponibles pour étudier les programmes probabilistes d’ordre supérieur : les automates probabilistes, le lambda calcul probabiliste, les modèles dénotationnels… pour adapter à l’étude de distance entre programmes les techniques existantes pour prouver l’équivalence de programmes, comme la trace-équivalence et la bisimulation.

« Je suis forcément très contente d’avoir obtenu le prix Gilles Kahn, s’enthousiasme Raphaëlle Crubillé. Je dois beaucoup à mes directeurs de thèses, qui se sont beaucoup investis. Et puis quand on rédige sa thèse, on a moins le temps de participer aux colloques et on s’isole un peu de la communauté scientifique. Ce prix reforme le lien en donnant aux chercheurs l’envie de lire ma thèse. »