Sémantique Opérationnelle
La sémantique opérationnelle définit la signification d'un programme en spécifiant son mode d'exécution, à l'aide de règles d'inférence qui décrivent les étapes du calcul.
Definition
La sémantique opérationnelle spécifie la signification d'un programme comme la séquence des étapes de calcul qu'il exécute, donnée par des relations de transition définies inductivement sur les configurations de programme.
Scope
Ce sujet aborde les sémantiques opérationnelles à petits pas (structurelle) et à grands pas (naturelle), où les relations de transition ou d'évaluation définies par des règles d'inférence dirigées par la syntaxe décrivent la manière dont les programmes effectuent leurs calculs. Il traite des stratégies de réduction, des machines abstraites, et de la façon dont les définitions opérationnelles soutiennent les preuves de sûreté de typage et d'équivalence de programmes.
Core questions
- Comment les règles d'inférence capturent-elles les étapes d'un calcul ?
- Quelle est la différence entre la sémantique à petits pas et la sémantique à grands pas ?
- Comment la sémantique opérationnelle soutient-elle les preuves de sûreté et d'équivalence ?
- Comment les machines abstraites se rapportent-elles aux définitions opérationnelles basées sur des règles ?
Key theories
- Sémantique opérationnelle structurelle
- Plotkin définit l'exécution par des règles de transition à petits pas structurées par la syntaxe du langage, offrant une description compositionnelle et dirigée par la syntaxe de la manière dont chaque construction calcule.
- Sémantique naturelle (à grands pas)
- La sémantique naturelle de Kahn relie un programme directement à son résultat final par des règles d'évaluation, en faisant abstraction des étapes intermédiaires et en facilitant certaines preuves.
Clinical relevance
La sémantique opérationnelle constitue l'outil standard pour spécifier le comportement réel des langages et prouver la correction des compilateurs et des interpréteurs. Son style basé sur des règles correspond étroitement aux implémentations et sous-tend la métathéorie des langages vérifiée par machine.
History
Les idées opérationnelles sont apparues dans les premières définitions de langages basées sur des interpréteurs. Les notes d'Aarhus de Plotkin en 1981 ont établi la sémantique opérationnelle structurelle comme un cadre rigoureux et dirigé par la syntaxe, et la sémantique naturelle de Kahn en 1987 a proposé une alternative à grands pas. Ensemble, elles sont devenues l'approche dominante pour définir et raisonner sur les langages de programmation.
Debates
- Formulations à petits pas versus à grands pas
- Les sémanticiens choisissent entre la sémantique à petits pas, qui expose les états intermédiaires et gère naturellement la non-terminaison et la concurrence, et la sémantique à grands pas, qui est concise mais moins adaptée aux calculs divergents ou entrelacés.
Key figures
- Gordon Plotkin
- Gilles Kahn
- Glynn Winskel
- Matthias Felleisen
Related topics
Seminal works
- plotkin1981
- kahn1987
- winskel1993
Frequently asked questions
- Quelle est la différence entre la sémantique à petits pas et la sémantique à grands pas ?
- La sémantique à petits pas décrit les étapes de calcul individuelles et les états intermédiaires entre elles, tandis que la sémantique à grands pas relie un programme directement à sa valeur finale, masquant les étapes intermédiaires.
- Pourquoi la sémantique opérationnelle est-elle utile pour prouver la sûreté ?
- Parce qu'elle rend explicites les étapes d'exécution, elle s'associe naturellement à la méthode de progression et de préservation, qui raisonne sur la manière dont le typage est maintenu à chaque étape d'un programme.