Un environnement pour la programmation avec types dépendants

Overview & Synopsis

Les systèmes basés sur la Théorie des Types prennent une importance considérable tant pour la vérification de programmes qu'en tant qu'outils permettant la preuve formelle de théorèmes mettant en jeu des calculs complexes. Ces systèmes nécessitent aujourd'hui une grande expertise pour être utilisés efficacement. Nous développons des constructions de haut niveau permettant d'utiliser les langages basés sur les théories des types dépendants aussi simplement que les langages de programmation fonctionnels usuels, sans sacrifier pour autant la richesse des constructions disponibles dans les premiers. Nous étudions un nouveau langage permettant l'écriture de programmes certifiés en ne donnant que leur squelette algorithmique et leur spécification. Le typage dans ce système donne lieu à la génération automatique d'obligations de preuve pouvant être résolues a posteriori. Nous démontrons les propriétés métathéoriques essentielles du système, dont les preuves sont partiellement mécanisées, et détaillons son implémentation dans l'assistant de preuve Coq. D'autre part, nous décrivons l'intégration et l'extension d'un système de "Type Classes" venu d'Haskell à Coq via une simple interprétation des constructions liées aux classes dans la théorie des types sous-jacente. Nous démontrons l'utilité des classes de types dépendantes pour la spécification et la preuve et présentons une implémentation économique et puissante d'une tactique de réécriture généralisée basée sur les classes. Nous concluons par la mise en œuvre de l'ensemble de ces contributions lors du développement d'une bibliothèque certifiée de manipulation d'une structure de données complexe, les "Finger Trees".