Ce document donne un panorama de la représentation des définitions inductives dans différents assistants de preuve en logique d'ordre supérieur, théorie des ensembles et théorie des types. Il présente, étudie et justifie les choix faits dans le système Coq.

Nous nous intéressons ici à la génération de programmes certifiés<br />corrects par construction. Ces programmes sont obtenus en<br />extrayant l'information pertinente de preuves constructives réalisées<br />dans l'assistant de preuves Coq.<br /><br />Une telle traduction, ou "extraction", des preuves constructives<br />en programmes fonctionnels n'est pas nouvelle, elle correspond <br />à un isomorphisme bien connu sous le nom de Curry-Howard. Et<br />l'assistant Coq comporte depuis longtemps un tel outil d'extraction. <br />Mais l'outil précédent présentait d'importantes limitations. Certaines <br />preuves Coq étaient ainsi hors de son champ d'application, alors que <br />d'autres engendraient des programmes incorrects.<br /><br />Afin de résoudre ces limitations, nous avons effectué une refonte<br />complète de l'extraction dans Coq, tant du point de vue de la théorie<br />que de l'implantation. Au niveau théorique, cette refonte a entraîné<br />la réalisation de nouvelles preuves de correction de ce mécanisme<br />d'extraction, preuves à la fois complexes et originales. Concernant<br />l'implantation, nous nous sommes efforcés d'engendrer du code <br />extrait efficace et réaliste, pouvant en particulier être intégré dans des<br />développement logiciels de plus grande échelle, par le biais de<br />modules et d'interfaces.<br /><br />Enfin, nous présentons également plusieurs études de cas illustrant<br />les possibilités de notre nouvelle extraction. Nous décrivons ainsi la<br />certification d'une bibliothèque modulaire d'ensembles finis, et <br />l'obtention de programmes d'arithmétique réelle exacte à partir d'une <br />formalisation d'analyse réelle constructive. Même si des progrès <br />restent encore à obtenir, surtout dans ce dernier cas, ces exemples <br />mettent en évidence le chemin déjà parcouru.