À quelles questions la sémantique dénotationnelle peut-elle répondre que la sémantique opérationnelle ne peut pas?

14

Je connais la sémantique opérationnelle (petite et grande étape) pour définir les langages de programmation. Je suis également intéressé à apprendre la sémantique dénotationnelle, mais je ne sais pas si cela en vaudra la peine. Vais-je simplement apprendre le même matériel d'un point de vue différent, ou y a-t-il des idées que je ne peux acquérir qu'en comprenant la sémantique dénotationnelle?

semantics operational-semantics denotational-semantics gardenhead
la source

11

Il n'y a pas vraiment d'accord sur ce qui caractérise la sémantique dénotationnelle (voir aussi cet article), si ce n'est qu'elle doit être compositionnelle . Cela signifie que si est la fonction sémantique, mappant les programmes à leur signification, quelque chose comme ce qui suit doit être le cas pour tous lesconstructeurs de programmes -aires et tous les programmes , ..., (en supposant implicitement un bon typage): $\newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack} \SEMB{\cdot}$ $n$ $f$ $M_1$ $M_n$

[[F (M_{1}, . . ., M_{n})]] = t r une n s (F) ([[M_{1}]], . . ., [[M_{n}]])

$\SEMB{f(M_1, ..., M_n)} = trans(f) (\SEMB{M_1}, ..., \SEMB{M_n})$

Ici est le constructeur correspondant à dans le domaine sémantique. La compositionnalité est similaire au concept d'homomorphisme en algèbre. $trans(f)$ $f$

La sémantique opérationnelle n'est pas compositionnelle dans ce sens. Historiquement, la sémantique dénotationnelle a été développée en partie parce que la sémantique opérationnelle n'était pas compositionnelle. Après la percée de la sémantique dénotationnelle théorique de l'ordre de D. Scott de -calculus, la plupart des sémantiques dénotationnelles étaient auparavant de la théorie de l'ordre. J'imagine que - en dehors de l'intérêt intellectuel pur - la sémantique dénotationnelle a été principalement inventée parce qu'à l'époque (années 1960): $\lambda$

Avant, il était difficile de raisonner sur la sémantique opérationnelle.
Autrefois, il était difficile de donner une sémantique axiomatique à des langages non triviaux.

Le problème tient en partie au fait que la notion d’égalité des programmes n’est pas aussi bien comprise qu’aujourd’hui. Je dirais que les deux problèmes ont été considérablement améliorés, (1) par exemple par des techniques basées sur la bisimilation provenant de la théorie des processus (qui peuvent être considérées comme une forme spécifique de sémantique opérationnelle) ou par exemple Pitts travaille sur la sémantique opérationnelle et le programme l'équivalence, et (2) par les développements, par exemple, de la logique de séparation ou des logiques de Hoare dérivées sous forme de versions typées des logiques de Hennessy-Milner via des intégrations de langage de programmation dans des π-calculs typés. Notez que la logique du programme (= sémantique axiomatique) est également compositionnelle.

Une autre façon de voir la sémantique dénotationnelle est qu'il existe de nombreux langages de programmation et ils se ressemblent tous, donc peut-être pouvons-nous trouver un méta-langage simple, mais universel, et mapper tous les langages de programmation de manière compositionnelle à cette méta- Langue. Dans les années 1960, on pensait que certains -calculus typés étaient ce méta-langage. Une image peut dire plus de 1000 mots: $\lambda$

Quel est l'avantage de cette approche? Peut-être qu'il est logique de le regarder à partir d'un PDV économique. Si nous voulons prouver quelque chose d'intéressant sur une classe de programme objet, nous avons deux options.

Prouvez-le directement au niveau de l'objet.
Prouvez que la traduction au méta-niveau (et retour) «préserve» la propriété, puis prouvez-la pour le méta-niveau, puis repoussez le résultat au niveau objet.

Le coût combiné de ce dernier est probablement plus élevé que le coût du premier, mais le coût de la preuve de la traduction peut être amorti sur toutes les utilisations futures, tandis que le coût de la preuve de la propriété pour le méta-niveau est beaucoup plus faible que celui de la preuve au niveau de l'objet.

L'approche originale de la théorie de l'ordre à la sémantique dénotationnelle n'a jusqu'à présent pas été à la hauteur de cette promesse, car les fonctionnalités de langage compliquées telles que l'orientation des objets, la concurrence et le calcul distribué n'ont pas encore reçu de sémantique de la théorie de l'ordre précise. Par «précis», j'entends une sémantique qui correspond à la sémantique opérationnelle naturelle de ces langages.

Vaut-il la peine d'apprendre la sémantique dénotationnelle? Si vous parlez d'approches théoriques de l'ordre de la sémantique dénotationnelle, ce n'est probablement pas le cas, sauf si vous voulez travailler dans la théorie des langages de programmation et devez comprendre des articles plus anciens. Une autre raison d'apprendre des approches théoriques de l'ordre de la sémantique dénotationnelle est la beauté de cette approche.

Martin Berger
la source

4

$O(p,\sigma)$ $\sigma'$ $\langle p, \sigma \rangle \to \sigma'$ $\bot$ $D(p)$ $p$ $O(p,\sigma)=D(p)(\sigma)$ $S(p)$ $\sigma\mapsto O(p,\sigma)$ $D(p)$

$C:X \to X'$ $S(C(p))=S'(p)$ $p$ $\sigma$ $O(C(p),\sigma)=O'(p,\sigma)$ $p$ $D(C(p))=D'(p)$ $\sigma$

Exemple idiot:

$C(p)=$ $(q;q')$ $(skip;q;skip;q';skip)$

$p$ $C$

xavierm02
la source

À quelles questions la sémantique dénotationnelle peut-elle répondre que la sémantique opérationnelle ne peut pas?

Réponses: