Sémantique axiomatique et logiques de programme
La sémantique axiomatique caractérise les programmes par des assertions logiques concernant leurs états, la logique de Hoare et ses successeurs fournissant des règles pour prouver la correction des programmes.
Definition
La sémantique axiomatique spécifie la signification d'un programme par les assertions logiques qui sont valides avant et après son exécution, et une logique de programme est un système déductif de règles d'inférence pour prouver de telles assertions concernant les programmes.
Scope
Ce sujet couvre le raisonnement sur les programmes au moyen d'assertions logiques : les triplets de Hoare reliant les préconditions, les programmes et les postconditions ; les transformateurs de prédicats et les préconditions les plus faibles de Dijkstra ; et la logique de séparation pour les programmes avec un état de tas (heap) mutable et partagé. Il aborde la correction partielle et totale, les invariants de boucle, ainsi que la complétude et la correction (soundness) des logiques de programme.
Core questions
- Comment un programme peut-il être prouvé correct par rapport à une spécification ?
- Qu'est-ce qu'un invariant de boucle et pourquoi est-il central pour la vérification ?
- Comment les transformateurs de prédicats calculent-ils les conditions nécessaires à la correction ?
- Comment peut-on raisonner de manière modulaire sur des programmes qui modifient une mémoire de tas (heap) partagée ?
Key theories
- Logique de Hoare
- Hoare a introduit un système axiomatique de règles d'inférence sur des triplets {P} C {Q}, fournissant une méthode compositionnelle pour prouver qu'un programme satisfait sa spécification.
- Préconditions les plus faibles et commandes gardées
- La sémantique des transformateurs de prédicats de Dijkstra définit la précondition la plus faible qui garantit qu'un programme atteint une postcondition, soutenant la dérivation systématique de programmes corrects.
- Logique de séparation
- Reynolds et O'Hearn ont étendu la logique de Hoare avec une conjonction de séparation qui permet un raisonnement local et modulaire sur les programmes manipulant des structures de données mutables partagées et des pointeurs.
Clinical relevance
Les logiques de programme sont l'épine dorsale de la vérification déductive de programmes, utilisées dans des outils qui prouvent la correction de logiciels critiques et dans des preuves mécanisées de composants de systèmes d'exploitation et de compilateurs. La logique de séparation, en particulier, a rendu possible la vérification évolutive du code manipulant des pointeurs.
History
La méthode de Floyd de 1967, consistant à attribuer des significations aux organigrammes, et la base axiomatique de Hoare de 1969 ont fondé le domaine. Le calcul des préconditions les plus faibles de Dijkstra dans les années 1970 a lié la vérification à la dérivation de programmes. La logique de séparation de Reynolds et O'Hearn, vers 2000, a revitalisé la logique de programme pour le code manipulant le tas (heap), menant à de puissants cadres de vérification modernes.
Debates
- Effort de vérification versus assurance
- Une question persistante est de savoir comment équilibrer l'effort manuel substantiel d'écriture des spécifications et des invariants avec les fortes garanties de correction que la vérification déductive procure, motivant l'automatisation et des méthodes plus légères.
Key figures
- C. A. R. Hoare
- Robert Floyd
- Edsger Dijkstra
- John Reynolds
- Peter O'Hearn
Related topics
Seminal works
- hoare1969
- dijkstra1975
- reynolds2002
- floyd1967
Frequently asked questions
- Qu'est-ce qu'un triplet de Hoare ?
- Un triplet de Hoare {P} C {Q} affirme que si la précondition P est vraie avant l'exécution de la commande C, alors la postcondition Q est vraie après (pour la correction partielle, à condition que C se termine).
- Pourquoi la logique de séparation est-elle importante ?
- La logique de séparation permet aux preuves de raisonner indépendamment sur des régions disjointes du tas (heap), rendant ainsi possible la vérification modulaire de programmes avec des pointeurs et un état mutable partagé.