Sciences du logiciel - Xavier Leroy
Collège de France
Écrire un petit programme informatique est facile. Concevoir et réaliser un logiciel complet qui soit fiable, pérenne et résistant aux attaques reste extraordinairement difficile. C'est le but des sciences du logiciel que de concevoir et développer les principes, les formalismes mathématiques, les techniques empiriques et les outils informatiques nécessaires pour concevoir, programmer et vérifier des logiciels fiables et sécurisés.L'enseignement de la chaire Sciences du logiciel vise à explorer cette problématique et à présenter la recherche contemporaine dans ce domaine. Le cours privilégie les approches dites « formelles », par opposition à l'empirisme souvent de mise en génie logiciel. Ces approches s'appuient sur des fondements mathématiquement rigoureux, connus ou en émergence : sémantiques formelles, logiques de programmes, systèmes déductifs, équivalences de programmes, calculs de processus… Historiquement, ces concepts ont émergé de considérations de programmation très terre-à-terre avant de se parer de rigueur mathématique. Le cours s'efforce de retracer ce cheminement des idées en partant de l'intuition du programmeur et en allant jusqu'à la mécanisation de ces approches formelles.Les premières années de cet enseignement auraient pu s'intituler « Programmer, démontrer », car ils ont exploré plusieurs modes d'interaction entre la programmation de logiciels et la démonstration d'énoncés mathématiques : programmer puis démontrer, comme dans les logiques de programmes pour la vérification déductive ; programmer pour démontrer, comme dans les logiques constructives et l'assistant à la démonstration Coq ; enfin, programmer égale démontrer, comme dans la féconde correspondance de Curry-Howard, objet de la première année du cours.La recherche de la chaire Sciences du logiciel s'effectue dans le cadre de l'équipe-projet Cambium, commune avec l'Inria. Les travaux de l'équipe visent à améliorer la fiabilité, la sûreté et la sécurité du logiciel en faisant progresser les langages de programmation et les méthodes de vérification formelle de programmes. Les principaux thèmes de recherche sont les systèmes de types et les algorithmes d'inférence de types, la vérification déductive de programmes, le parallélisme à mémoire partagée, et les modèles mémoires faiblement cohérents. L'équipe conçoit et développe deux grands logiciels de recherche qui intègrent et font passer dans la pratique bon nombre de ses résultats : OCaml, un langage de programmation fonctionnel statiquement typé et son implémentation, et CompCert, un compilateur formellement vérifié pour logiciels embarqués critiques.
Episodes
Mentioned books
Apr 13, 2023 • 1h 18min
06 - Structures de données persistantes : De la dérivation formelle à la navigation dans une structure : contextes, zippers, index, etc.
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesDe la dérivation formelle à la navigation dans une structure : contextes, zippers, index, etc.Il est souvent utile de pouvoir désigner une partie d'une structure de données (par exemple, un sous-arbre d'un arbre) et opérer sur cette partie de manière locale. Dans les algèbres de termes, cela se modélise à l'aide de contextes. Cependant, les « zippers » de Huet, une présentation duale des contextes, permet de se déplacer dans un terme de manière algorithmiquement efficace. Nous verrons comment les types des contextes et des zippers s'obtiennent systématiquement à partir d'un type algébrique en utilisant les mêmes règles que pour la dérivation de fonctions à une variable. Nous ferons ensuite le lien entre zippers et index (« fingers »), une technique algorithmique classique pour tenir à jour des pointeurs à l'intérieur d'un arbre.
Apr 7, 2023 • 54min
Séminaire - KC Sivaramakrishnan : Mergeable Replicated Data Types
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesSéminaire - KC Sivaramakrishnan : Mergeable Replicated Data TypesReplicated data types (RDTs) are specialised data structures that allow for concurrent modification of multiple replicas, even when they are geographically dispersed, without requiring coordination between them. However, constructing efficient and correct RDTs is challenging due to the complexity involved in reasoning about independently evolving states of replicas and resolving conflicts between them.In this talk, I will introduce Mergeable Replicated Data Types (MRDTs), a practical approach to constructing and verifying RDTs that is both efficient and correct. MRDTs build on the concept of a distributed version control system like Git, but extend it to arbitrary data types rather than just files. The key idea is to make sequential data types suitable for distribution by equipping them with a three-way merge function that reconciles conflicting versions. I will discuss how this merge function captures the complexities of distribution, simplifying both implementation and verification. Furthermore, I will discuss the critical role played by persistent data structures in MRDTs, as well as the inherent trade-off between persistence and efficiency in distributed data stores.
Apr 7, 2023 • 1h 17min
05 - Structures de données persistantes : Systèmes de numération et types non réguliers
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesSystèmes de numération et types non réguliersUn système de numération permet de représenter efficacement de grands nombres en donnant des poids différents aux chiffres successifs (par exemple, 1, 10, 100, 1 000, etc.). Cette idée inspire aussi la conception de structures persistantes remarquablement efficaces, notamment pour les listes à accès direct et les files de priorité. Nous décrirons ensuite l'utilisation de types algébriques non réguliers pour implémenter de telles structures de manière plus simple et mieux contrôlée par le typage. Nous terminerons par l'étude des « finger trees » de Hinze et Paterson, une structure polyvalente qui applique plusieurs de ces techniques.
Mar 30, 2023 • 50min
Séminaire - Jean-Christophe Filliatre : Structures de données semi-persistantes
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesSéminaire - Jean-Christophe Filliatre : Structures de données semi-persistantes
Mar 30, 2023 • 1h 17min
04 - Structures de données persistantes : Comment rendre persistante une structure impérative ?
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesConcilier amortissement et persistance : de l'importance de la paresseDans ce cours, nous nous intéresserons aux structures de données persistantes dont l'implémentation utilise « sous le capot » des structures impératives et de la mutation en place, tout en préservant une interface purement fonctionnelle. Nous partirons des tableaux fonctionnels de Baker, qui combinent un tableau impératif et des liste de différences, puis introduirons progressivement la technique des « fat nodes » de Driscoll, Sarnak, Sleator et Tarjan, qui donne un procédé systématique pour rendre persistante une structure d'arbre impérative.
Mar 23, 2023 • 50min
Séminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexity
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesSéminaire - Tobias Nipkow : Verification of functional data structures: Correctness and complexityThe talk gives a brief overview of our book "Functional Algorithms, Verified!" and its approach to verifying not just correctness but also running time of a large collection of functional algorithms. Then, two examples are presented in more detail: real time queues and double-ended queues that are implemented purely functionally with the help of stacks and whose operations have guaranteed constant running time.
Mar 23, 2023 • 1h 17min
03 - Structures de données persistantes : Concilier amortissement et persistance : de l'importance de la paresse
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesConcilier amortissement et persistance : de l'importance de la paresseL'amortissement est un principe de conception de structures de données qui vise à garantir un coût moyen par opération sur toute séquence d'opérations, le coût élevé de certaines opérations étant amorti par le coût faible d'opérations précédentes. Après un rappel des principes de l'amortissement et de l'analyse en temps amorti, le cours montrera des exemples de structures de données persistantes qui ont une complexité O(1) à condition d'être utilisées de manière linéaire. Nous étudierons ensuite l'approche d'Okasaki pour concilier amortissement et persistance générale (non linéaire), utilisant l'évaluation paresseuse (à la demande) de certains calculs.
Mar 16, 2023 • 1h 25min
02 - Structures de données persistantes : Arbres équilibrés + copie de branches = persistance
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesArbres équilibrés + copie de branches = persistanceCopier et modifier une branche d'un arbre équilibré, tout en partageant les sous-arbres non modifiés avec l'arbre d'origine, est une technique simple et générale pour construire de nombreuses structures de données persistantes ayant des complexités O(log n). Le cours montrera cette technique à l'œuvre sur des structures de type « dictionnaire » : arbres de recherche, arbres préfixes, arbres préfixes avec hachage (HAMT), arbres de Braun, etc.
Mar 9, 2023 • 1h 18min
01 - Structures de données persistantes : Introduction aux structures persistantes et à la programmation purement fonctionnelle
Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesIntroduction aux structures persistantes et à la programmation purement fonctionnelleCe premier cours décrira l'émergence des structures de données persistantes dans deux contextes historiques différents : l'émergence des langages de programmation purement fonctionnels et de leurs approches équationnelles de dérivation et de vérification des programmes, d'une part, et de l'autre l'apparition de besoins nouveaux, notamment en algorithmique géométrique, de partager efficacement les représentations en mémoire de plusieurs structures de données qui diffèrent en peu de points. Nous verrons au passage nos premiers exemples de structures persistantes, à base de listes, d'arbres binaires, ou de tableaux avec historiques de modifications.
Apr 21, 2022 • 1h 4min
07 - Sécurité du logiciel : quel rôle pour les langages de programmation ?
Xavier LeroyCollège de FranceScience du logicielAnnée 2021-2022Sécurité du logiciel : quel rôle pour les langages de programmation ?Compiler un programme source en code machine peut être l'occasion de le rendre plus résistant à certaines attaques. Cependant, de nombreuses optimisations de compilation, pourtant sémantiquement correctes, peuvent affaiblir la sécurité du programme. Nous verrons comment caractériser ces différences de sécurité entre un fragment de programme source et son code compilé à l'aide d'outils sémantiques classiques : l'équivalence observationnelle et le problème de la full abstraction. Nous présenterons quelques approches qui ont été proposées pour compiler tout en préservant les équivalences observationnelles.
