Sémantique dénotationnelle
La sémantique dénotationnelle interprète les programmes comme des objets mathématiques, généralement des fonctions sur des domaines structurés, offrant une explication compositionnelle et indépendante de la machine du sens.
Definition
La sémantique dénotationnelle attribue à chaque programme un objet mathématique (sa dénotation), défini de manière compositionnelle à partir des dénotations de ses parties, la récursion étant interprétée via les points fixes les moins dans les domaines.
Scope
Ce sujet couvre l'approche de Scott-Strachey, dans laquelle chaque fragment de programme dénote un élément d'un domaine mathématique. Il inclut la théorie des domaines, les ordres partiels complets, les fonctions continues et les interprétations du point fixe le moins pour la récursion, ainsi que l'abstraction complète, qui concerne la correspondance étroite entre le sens dénotationnel et le comportement observable.
Core questions
- Quelles structures mathématiques peuvent modéliser la récursion arbitraire et la non-terminaison ?
- Comment le sens est-il construit de manière compositionnelle à partir des sens des sous-programmes ?
- Qu'est-ce que l'abstraction complète et pourquoi est-elle difficile à atteindre ?
- Comment le sens dénotationnel est-il lié au comportement opérationnel ?
Key theories
- Théorie des domaines et sémantique des points fixes
- La théorie des domaines de Scott fournit des structures ordonnées et des fonctions continues dans lesquelles les définitions récursives sont interprétées comme les points fixes les moins, résolvant le problème de donner un sens aux programmes auto-référentiels.
- Abstraction complète
- L'étude de LCF par Plotkin a formulé le problème de l'abstraction complète, à savoir si l'égalité dénotationnelle coïncide exactement avec l'équivalence observationnelle, révélant une lacune qui a motivé des décennies de recherches supplémentaires.
Clinical relevance
Les modèles dénotationnels offrent une référence précise et compositionnelle pour le sens des langages, soutiennent le raisonnement sur l'équivalence et l'optimisation des programmes, et éclairent la conception de fonctionnalités telles que la récursion et les fonctions d'ordre supérieur. La théorie des domaines relie également les langages de programmation à des domaines plus vastes des mathématiques et de la logique.
History
Les travaux de Strachey sur les descriptions mathématiques des langages et la construction par Scott en 1969 de modèles de domaines ont lancé la sémantique dénotationnelle, formalisée dans leur article de 1971. La théorie des domaines de Scott a mûri tout au long des années 1970, et l'analyse de LCF par Plotkin a cristallisé le problème de l'abstraction complète, qui a stimulé des développements ultérieurs tels que la sémantique des jeux.
Debates
- Le problème de l'abstraction complète
- Une question centrale est de savoir si un modèle dénotationnel peut capturer exactement le comportement observable d'un langage, ni plus ni moins ; les modèles de domaines classiques échouent à cela pour les langages séquentiels d'ordre supérieur, ce qui a incité à développer des modèles alternatifs.
Key figures
- Dana Scott
- Christopher Strachey
- Gordon Plotkin
- Glynn Winskel
Related topics
Seminal works
- scott1971
- scott1976
- plotkin1977
- winskel1993
Frequently asked questions
- Qu'est-ce qu'un domaine en sémantique dénotationnelle ?
- Un domaine est une structure mathématique, généralement un ensemble partiellement ordonné avec des limites de chaînes croissantes, qui fournit un cadre où les calculs récursifs et partiels peuvent être modélisés comme les points fixes les moins de fonctions continues.
- Qu'est-ce que l'abstraction complète ?
- Une sémantique est pleinement abstraite lorsque deux programmes ont la même dénotation exactement lorsqu'ils sont observationnellement équivalents, ce qui signifie que le modèle ne distingue pas les programmes comportementalement identiques et ne confond pas ceux qui sont distinguables.