Sémantique opérationnelle – Wikipedia wiki

Posted on January 5, 2017 by lordneo

before-content-x4

Catégorie de la sémantique de langage de programmation formelle

after-content-x4

Sémantique opérationnelle est une catégorie de sémantique formelle de langue de programmation dans laquelle certaines propriétés souhaitées d’un programme, telles que l’exactitude, la sécurité ou la sécurité, sont vérifiées en construisant des preuves à partir de déclarations logiques sur son exécution et ses procédures, plutôt que en attachant des significations mathématiques à ses termes (dénotation sémantique). La sémantique opérationnelle est classée en deux catégories: Sémantique opérationnelle structurelle (ou Sémantique en petit pas ) décrivez officiellement comment le étapes individuelles d’un calcul se déroule dans un système informatique; par opposition sémantique naturelle (ou sémantique en gros ) Décrivez comment le résultats globaux des exécutions sont obtenues. Les autres approches pour fournir une sémantique formelle des langages de programmation comprennent la sémantique axiomatique et la sémantique dénotationnelle.

La sémantique opérationnelle pour un langage de programmation décrit comment un programme valide est interprété comme des séquences d’étapes de calcul. Ces séquences alors sont la signification du programme. Dans le contexte de la programmation fonctionnelle, la dernière étape d’une séquence de terminaison renvoie la valeur du programme. (En général, il peut y avoir de nombreuses valeurs de retour pour un seul programme, car le programme peut être non déterministe, et même pour un programme déterministe, il peut y avoir de nombreuses séquences de calcul car la sémantique peut ne pas spécifier exactement quelle séquence d’opérations arrive à cette valeur.)

La première incarnation formelle de sémantique opérationnelle a peut-être été l’utilisation du calcul Lambda pour définir la sémantique de Lisp. ^[d’abord]Les machines abstraites dans la tradition de la machine SECD sont également étroitement liées.

Table of Contents

Histoire [ modifier ]]

Le concept de sémantique opérationnelle a été utilisé pour la première fois dans la définition de la sémantique d’Algol 68.
La déclaration suivante est une citation du rapport révisé d’Algol 68:

La signification d’un programme dans la langue stricte est expliquée en termes d’ordinateur hypothétique
qui exécute l’ensemble des actions qui constituent l’élaboration de ce programme. (Algol68, section 2)

La première utilisation du terme «sémantique opérationnelle» dans sa signification actuelle est attribuée à
Dana Scott (Plotkin04).
Ce qui suit est une citation du papier séminal de Scott sur la sémantique formelle,
dans lequel il mentionne les aspects “opérationnels” de la sémantique.

after-content-x4

Il est très bien de viser une approche plus «abstraite» et «plus propre»
sémantique, mais si le plan doit être bon, les aspects opérationnels ne peuvent pas
être complètement ignoré. (Scott70)

Approches [ modifier ]]

Gordon Plotkin a présenté la sémantique opérationnelle structurelle, Matthias Felleisen et Robert Hieb The Reduction Semantics, ^[2]et Gilles Kahn la sémantique naturelle.

Sémantique en petit pas [ modifier ]]

Sémantique opérationnelle structurelle [ modifier ]]

Sémantique opérationnelle structurelle (SOS, également appelé Sémantique opérationnelle structurée ou Sémantique en petit pas ) a été introduit par Gordon Plotkin dans (Plotkin81) comme moyen logique pour définir la sémantique opérationnelle. L’idée de base derrière SOS est de définir le comportement d’un programme en termes de comportement de ses parties, offrant ainsi une vision structurelle, c’est-à-dire orientée syntaxe et inductive, sur la sémantique opérationnelle. Une spécification SOS définit le comportement d’un programme en termes de relation (s) de transition (s) (s). Les spécifications SOS prennent la forme d’un ensemble de règles d’inférence qui définissent les transitions valides d’un morceau de syntaxe composite en termes de transitions de ses composants.

Pour un exemple simple, nous considérons une partie de la sémantique d’un simple langage de programmation; Des illustrations appropriées sont données dans Plotkin81 et Hennessy90 et dans d’autres manuels. Laisser

{displayStyle c_ {1}, c_ {2}}

$C_{1},C_{2}$ s’étendre sur les programmes de la langue et laisser

{DisplayStyle S}

$s$ plage sur les états (par exemple, fonctions des emplacements de mémoire aux valeurs). Si nous avons des expressions (variées par

{displaystyle e}

$E$ ), valeurs (

{DisplayStyle V}

$V$ ) et les emplacements (

{displaystyle l}

$L$ ), alors une commande de mise à jour de la mémoire aurait une sémantique:

{displayStyle {frac {langle e, srangle rightarrow v} {langle l: = e ,,, srangle longRightarrow (Suplus (lmapsto v))}}}

${frac {langle E,srangle Rightarrow V}{langle L:=E,,,srangle longrightarrow (suplus (Lmapsto V))}}$

De manière informelle, la règle dit que ” si l’expression

{displaystyle e}

$E$ en état

{DisplayStyle S}

$s$ réduit la valeur

{DisplayStyle V}

$V$ , alors le programme

{displayStyle l: = e}

$L:=E$ mettra à jour l’état

{DisplayStyle S}

$s$ avec l’affectation

{displayStyle l = v}

$L=V$ “.

La sémantique du séquençage peut être donnée par les trois règles suivantes:

{displaystyle {frac {langle C_{1},srangle longrightarrow s’}{langle C_{1};C_{2},,srangle longrightarrow langle C_{2},s’rangle }}quad quad {frac {langle C_{1},srangle longrightarrow langle C_{1}’,s’rangle }{langle C_{1};C_{2},,srangle longrightarrow langle C_{1}’;C_{2},,s’rangle }}quad quad {frac {}{langle mathbf {skip} ,srangle longrightarrow s}}}

${frac {langle C_{1},srangle longrightarrow s'}{langle C_{1};C_{2},,srangle longrightarrow langle C_{2},s'rangle }}quad quad {frac {langle C_{1},srangle longrightarrow langle C_{1}',s'rangle }{langle C_{1};C_{2},,srangle longrightarrow langle C_{1}';C_{2},,s'rangle }}quad quad {frac {}{langle {mathbf {skip}},srangle longrightarrow s}}$

De manière informelle, la première règle dit que,
Si le programme

{displayStyle c_ {1}}

$C_{1}$ en état

{DisplayStyle S}

$s$ finitions en état

{displaystyle s ‘}

$s'$ , puis le programme

{displayStyle c_ {1}; c_ {2}}

$C_{1};C_{2}$ en état

{DisplayStyle S}

$s$ se réduira au programme

{displayStyle c_ {2}}

$C_{2}$ en état

{displaystyle s ‘}

$s'$ .
(Vous pouvez considérer cela comme formalisation “vous pouvez courir

{displayStyle c_ {1}}

$C_{1}$ , puis courir

{displayStyle c_ {2}}

$C_{2}$ Utilisation du magasin de mémoire résultant.)
La deuxième règle dit que
Si le programme

{displayStyle c_ {1}}

$C_{1}$ en état

{DisplayStyle S}

$s$ peut réduire le programme

{displayStyle c_ {1} ‘}

$C_{1}'$ avec l’état

{displaystyle s ‘}

$s'$ , puis le programme

{displayStyle c_ {1}; c_ {2}}

$C_{1};C_{2}$ en état

{DisplayStyle S}

$s$ se réduira au programme

{displayStyle c_ {1} ‘; c_ {2}}

$C_{1}';C_{2}$ en état

{displaystyle s ‘}

$s'$ .
(Vous pouvez considérer cela comme formaliser le principe d’un compilateur d’optimisation:
“Vous êtes autorisé à vous transformer

{displayStyle c_ {1}}

$C_{1}$ comme s’il était autonome, même si ce n’est que le
Première partie d’un programme. “)
La sémantique est structurelle, car la signification du programme séquentiel

{displayStyle c_ {1}; c_ {2}}

$C_{1};C_{2}$ , est défini par le sens de

{displayStyle c_ {1}}

$C_{1}$ et le sens de

{displayStyle c_ {2}}

$C_{2}$ .

Si nous avons également des expressions booléennes sur l’État, passant par

{displaystyle b}

$B$ alors nous pouvons définir la sémantique du alors que commande:

{displayStyle {frac {Langle B, srangle rightarrow mathbf {true}} {langle mathbf {while} b mathbf {do} c, srangle longRightarrow langle c; mathbf {while} b mathbf {do} c, srangle}} quad {frac {langle b, srangle rightarrow mathbf {false}} {langle mathbf {while} b mathbf {do} c, srangle longRightarrow s}}}

${frac {langle B,srangle Rightarrow {mathbf {true}}}{langle {mathbf {while}} B {mathbf {do}} C,srangle longrightarrow langle C;{mathbf {while}} B {mathbf {do}} C,srangle }}quad {frac {langle B,srangle Rightarrow {mathbf {false}}}{langle {mathbf {while}} B {mathbf {do}} C,srangle longrightarrow s}}$

Une telle définition permet une analyse formelle du comportement des programmes, permettant l’étude des relations entre les programmes. Les relations importantes incluent les précommandes de simulation et la bisimulation.
Ceux-ci sont particulièrement utiles dans le contexte de la théorie de la concurrence.

Grâce à son look intuitif et sa structure facile à suivre,
SOS a gagné en popularité et est devenu une norme de facto pour définir
Sémantique opérationnelle. En signe de succès, le rapport original (soi-disant Aarhus
Rapport) sur SOS (Plotkin81) a attiré plus de 1 000 citations selon le Citaiser [d’abord] ,
En faire l’un des rapports techniques les plus cités en informatique.

Sémantique de réduction [ modifier ]]

Sémantique de réduction est une présentation alternative de la sémantique opérationnelle. Ses idées clés ont d’abord été appliquées à l’appel purement fonctionnel par leur nom et par appel par des variantes de valeur du calcul Lambda par Gordon Plotkin en 1975 ^[3]et généralisé aux langues fonctionnelles d’ordre supérieur avec des caractéristiques impératives de Matthias Felleisen dans sa thèse de 1987. ^[4]La méthode a été élaborée en outre par Matthias Felleisen et Robert Hieb en 1992 en une théorie pleinement équationnelle pour le contrôle et l’État. ^[2]L’expression «sémantique de réduction» elle-même a été inventée pour la première fois par Felleisen et Daniel Friedman dans un article de Parle 1987. ^[5]

La sémantique de réduction est donnée comme un ensemble de règles de réduction que chacun spécifie une seule étape de réduction potentielle. Par exemple, la règle de réduction suivante stipule qu’une déclaration d’affectation peut être réduite si elle se trouve immédiatement à côté de sa déclaration variable:

{displayStyle mathbf {let rec} x = v_ {1} mathbf {in} xleftarrow v_ {2}; e longRightArrow Mathbf {let rec} x = v_ {2} mathbf {in} e}

${displaystyle mathbf {let rec} x=v_{1} mathbf {in} xleftarrow v_{2}; e longrightarrow mathbf {let rec} x=v_{2} mathbf {in} e}$

Pour obtenir une instruction d’affectation dans une telle position, il est «bouillonnant» via les applications de fonction et le côté droit des instructions d’affectation jusqu’à ce qu’il atteigne le point approprié. Depuis l’intervention

{displayStyle Mathbf {LET}}

${displaystyle mathbf {let} }$ Les expressions peuvent déclarer des variables distinctes, le calcul exige également une règle d’extrusion pour

{displayStyle Mathbf {LET}}

${displaystyle mathbf {let} }$ expressions. La plupart des utilisations publiées de la sémantique de réduction définissent ces «règles de bulle» avec la commodité des contextes d’évaluation. Par exemple, la grammaire des contextes d’évaluation dans un simple appel d’appel par valeur peut être donné comme

Invite.sop ylext, yy: .. – | Ce n’est pas un imal.

${displaystyle E::=[,] {big |} v E {big |} E e {big |} xleftarrow E {big |} mathbf {let rec} x=v mathbf {in} E {big |} E; e}$

où

{displaystyle e}

$e$ indique des expressions arbitraires et

{DisplayStyle V}

$v$ indique des valeurs entièrement réduites. Chaque contexte d’évaluation comprend exactement un trou

{DisplayStyle [,]}

${displaystyle [,]}$ dans lequel un terme est branché de manière capturant. La forme du contexte indique ce trou où une réduction peut se produire. Pour décrire le «bouillonnement» à l’aide de contextes d’évaluation, un seul axiome suffit:

{displayStyle e [, xleftArrow v; e,] longRightarrow xleftarrow v; E [, e,] qquad {text {(ascension de lifting)}}}

${displaystyle E[,xleftarrow v; e,] longrightarrow xleftarrow v; E[,e,]qquad {text{(lift assignments)}}}$

Cette règle de réduction unique est la règle de levage de Felleisen et le calcul Lambda de Hieb pour les déclarations d’affectation. Les contextes d’évaluation restreignent cette règle à certains termes, mais il est librement applicable à n’importe quel terme, y compris sous Lambdas.

Suivant l’intrigue, montrant l’utilité d’un calcul dérivé d’un ensemble de règles de réduction exige (1) un lemme de l’église-rosser pour la relation en une seule étape, ce qui induit une fonction d’évaluation, et (2) un lemme de normalisation de curry-fey fermeture transitive-réflexive de la relation en une seule étape, qui remplace la recherche non déterministe dans la fonction d’évaluation par une recherche la plus à gauche / la plus extérieure déterministe. Felleisen a montré que les extensions impératives de ce calcul satisfont à ces théorèmes. Les conséquences de ces théorèmes sont que la théorie équationnelle – la fermeture symétrique-transitive-réflexive – est un principe de raisonnement solide pour ces langues. Cependant, dans la pratique, la plupart des applications de la sémantique de réduction se dispensent avec le calcul et utilisent uniquement la réduction standard (et l’évaluateur qui peut en être dérivé).

La sémantique de réduction est particulièrement utile compte tenu de la facilité par laquelle les contextes d’évaluation peuvent modéliser des constructions de contrôle étatiques ou inhabituelles (par exemple, les continuations de première classe). De plus, une sémantique de réduction a été utilisée pour modéliser les langues orientées objet, ^[6]Systèmes contractuels, exceptions, futures, appel par incendie et de nombreuses autres fonctionnalités linguistiques. Un traitement approfondi et moderne de la sémantique de réduction qui discute longuement de plusieurs applications de ce type est donné par Matthias Felleisen, Robert Bruce Findler et Matthew Flatt dans Ingénierie de sémantique avec plt redex . ^[7]

Sémantique en gros [ modifier ]]

Sémantique naturelle [ modifier ]]

La sémantique opérationnelle structurelle en grande étape est également connue sous les noms sémantique naturelle , sémantique relationnelle et sémantique d’évaluation . ^[8]La sémantique opérationnelle en grandeur a été introduite sous le nom sémantique naturelle par Gilles Kahn lors de la présentation du mini-ML, un dialecte pur de Ml.

On peut considérer les définitions en gros étapes comme des définitions des fonctions, ou plus généralement de relations, interprétant chaque construction de langage dans un domaine approprié. Son intuitivité en fait un choix populaire pour les spécifications de sémantique dans les langages de programmation, mais il présente certains inconvénients qui le rendent gênant ou impossible à utiliser dans de nombreuses situations, telles que les langages avec des caractéristiques ou une concurrence à forte intensité de contrôle.

Une sémantique en gros étapes décrit de manière divise et conquérir comment les résultats d’évaluation finaux des constructions linguistiques peuvent être obtenus en combinant les résultats d’évaluation de leurs homologues syntaxiques (sous-expressions, substactifs, etc.).

Comparaison [ modifier ]]

Il existe un certain nombre de distinctions entre la sémantique en petite étape et en grande étape qui influence si l’une ou l’autre forme une base plus appropriée pour spécifier la sémantique d’un langage de programmation.

La sémantique en gros étapes a l’avantage d’être souvent plus simple (nécessitant moins de règles d’inférence) et correspond souvent directement à une implémentation efficace d’un interprète pour la langue (d’où Kahn les appelant “naturels”.) Les deux peuvent conduire à des preuves plus simples, par exemple, par exemple Lors de la prouvance de la préservation de l’exactitude dans le cadre d’une transformation du programme. ^[9]

Le principal inconvénient de la sémantique en gros étapes est que les calculs non terminants (divergents) n’ont pas d’arbre d’inférence, ce qui rend impossible les énoncés et prouver les propriétés de ces calculs. ^[9]

La sémantique en petite étape donne plus de contrôle sur les détails et l’ordre d’évaluation. Dans le cas de la sémantique opérationnelle instrumentée, cela permet à la sémantique opérationnelle de suivre et du sémantiste à énoncer et à prouver des théorèmes plus précis sur le comportement d’exécution de la langue. Ces propriétés rendent la sémantique en petite étape plus pratique pour prouver la solidité de type d’un système de type contre une sémantique opérationnelle. ^[9]

Voir également [ modifier ]]

Les références [ modifier ]]

^ McCarthy, John. “Fonctions récursives des expressions symboliques et leur calcul par machine, partie I” . Archivé de l’original le 2013-10-04 . Récupéré 2006-10-13 .
^ ^un ^b Felleisen, M.; Hieb, R. (1992). “Le rapport révisé sur les théories syntaxiques du contrôle séquentiel et de l’état” . Informatique théorique . 103 (2): 235–271. est ce que je: 10.1016 / 0304-3975 (92) 90014-7 .
^ Plotkin, Gordon (1975). “Call-by-Name, Call-by-Value et le λ-calcul” (PDF) . Informatique théorique . d’abord (2): 125–159. est ce que je: 10.1016 / 0304-3975 (75) 90017-1 . Récupéré 22 juillet, 2021 .
^ Felleisen, Matthias (1987). Les calculs de la conversion lambda-v-cs: une théorie syntaxique du contrôle et de l’état dans les langages de programmation impératifs de haut niveau (PDF) (Doctorat). Université de l’Indiana . Récupéré 22 juillet, 2021 .
^ Felleisen, Matthias; Friedman, Daniel P. (1987). “Une sémantique de réduction pour les langues impératives d’ordre supérieur” Actes des architectures et langues parallèles Europe . Conférence internationale sur les architectures et langues parallèles Europe. Vol. 1. Springer-Verlag. pp. 206–223. est ce que je: 10 1007 / 3-540-17945-3_12 .
^ Abadi, M.; Cardelli, L. (8 septembre 2012). Une théorie des objets . ISBN 9781441985989 .
^ Felleisen, Matthias; Findler, Robert Bruce; Flatt, Matthew (2009). Ingénierie de sémantique avec plt redex . Le avec presse. ISBN 978-0-262-06275-6 .
^ Université de l’Illinois CS422
^ ^un ^b ^c Xavier Leroy. “Sémantique opérationnelle en grande étape coïncale”.

Dès la lecture [ modifier ]]

Gilles Kahn. “Sémantique naturelle”. Actes du 4e Symposium annuel sur les aspects théoriques de l’informatique . Springer Publishing House. Londres. 1987.
Gordon D. Plotkin. Une approche structurelle de la sémantique opérationnelle . (1981) Tech. Rep. Daimi FN-19, Département d’informatique, Université d’Aarhus, Aarhus, Danemark. (Réimprimé avec des corrections dans J. Log. Algebr. Programme. 60-61: 17-139 (2004), préimpression ).
Gordon D. Plotkin. Les origines de la sémantique opérationnelle structurelle. J. Log. Algebr. Programme. 60-61: 3-15, 2004. ( préimpression ).
Dana S. Scott. Aperçu d’une théorie mathématique du calcul, groupe de recherche en programmation, Technical Monograph PRG – 2, Oxford University, 1970.
Adrian van Wijngaarden et al. Rapport révisé sur la langue algorithmique Algool 68. IFIP. 1968. ( [2] ^{[ lien mort permanent ]]})
Matthew Hennessy. Sémantique des langages de programmation. Wiley, 1990. disponible en ligne .

Liens externes [ modifier ]]

after-content-x4

Sémantique opérationnelle – Wikipedia wiki

Histoire [ modifier ]]

Approches [ modifier ]]

Sémantique en petit pas [ modifier ]]

Sémantique opérationnelle structurelle [ modifier ]]

Sémantique de réduction [ modifier ]]

Sémantique en gros [ modifier ]]

Sémantique naturelle [ modifier ]]

Comparaison [ modifier ]]

Voir également [ modifier ]]

Les références [ modifier ]]

Dès la lecture [ modifier ]]

Liens externes [ modifier ]]

Recent Posts

Recent Comments

Archives

Categories

Meta