Raisonnement sur les boucles à terminaison non déterministe

10

Voici une question "piste B" s'il y en a jamais eu. Résumé: la première chose à laquelle je pense lorsque j'essaie de donner une sémantique à des programmes non déterministes se traduit par une sémantique où je ne peux pas prouver les choses sur les boucles qui ne terminent que la non-déterminisme. Certes, quelqu'un a trouvé quoi faire dans cette situation, ou du moins a souligné que c'est difficile, mais je ne sais pas comment le rechercher (d'où la balise "demande de référence").

Contexte

Je veux modéliser un tout-langage avec le non-déterminisme. Je pense que c'est la façon évidente (ou du moins naïve) de modéliser un tel langage avec un Powerdomain Smyth, mais corrigez-moi si je me trompe. Nous modéliserons la signification d'une commande dans ce langage comme une fonction dont le domaine est l'ensemble d'états et dont le codomaine est l'ensemble , où est le moindre élément représentant la non-terminaison et est le jeu de puissance des états.P ( S ) = { } P ( S ) P ( S )SP(S)={}P(S)P(S)

σ{σ1,σ2,}PQ

  • skipσ={σ}
  • x:=Eσ={σ[(Eσ)/x]}
  • abortσ=
  • if E then P else Qσ=Pσ if Eσ=true , sinon Qσ
  • PQσ= si Pσ= ou Qσ= , sinon PσQσ
  • P σ = Q T permet = T permet P σ T permet P σQ T permetP;Qσ= si ou pour certains , sinonPσ=Qτ=τPστPσQτ

Il y a un ordre partiel complet dirigé , où pour tout et si et sont tous deux des ensembles appropriés et , et nous pouvons l'étendre aux fonctions de à point par point: if pour chaque et est la fonction qui mappe chaque état sur .S S P ( S ) S 1S 2 S 1 S 2 S 1S 2 f S P ( S ) f 1f 2 f 1 ( σ ) f 2 ( σ ) σ f SSP(S)S1S2S1S2S1S2fSP(S)f1f2f1(σ)f2(σ)σf

La signification d'une boucle est est la plus borne supérieure de la chaîne , où si , sinon if ou pour certains , sinon . (Cette définition suppose que le je viens de définir est Scott continu, mais je pense qu'il est prudent de laisser cela de côté.)f f ( f ) f ( f ( f ) ) ... f ( g ) ( σ ) = { σ } E ( σ ) = f un l s eP σ = while E do Pσff(f)f(f(f))f(g)(σ)={σ}E(σ)=falsePσ=g(τ)=τ P σ g ( τ ) fτPστPσg(τ)f

Question

Considérez ce programme:

b : = t r u e ; w h i l e b d ox:=0;
b:=true;
while b do
x:=x+2;
b:=falseb:=true

Intuitivement, c'est une boucle qui peut retourner n'importe quel nombre pair positif ou ne pas se terminer, et cela correspond à ce que nous pouvons prouver à propos de cette boucle en utilisant la précondition libérale la plus faible (il est possible de montrer que est une boucle invariant). Cependant, parce que la boucle a la capacité de ne pas se terminer (nous pouvons affiner le choix non déterministe par le programme qui prend toujours la branche de droite), la signification de ce programme étant donné tout état initial est . (Moins officieusement: la fonction qui mappe tout état où est faux à lui-même et tout état où est vrai à est un point fixe du utilisé pour définir la boucle.)b b fn.x=2nbbf

Cela signifie que la sémantique naïve que j'ai proposée ne correspond pas à la façon dont je m'attends à pouvoir raisonner sur les programmes. Je blâme ma sémantique, mais je ne sais pas comment les corriger.

Rob Simmons
la source
4
Je pense qu'en utilisant comme codomaine de la signification d'un programme, vous avez effectivement abandonné tout raisonnement sur un programme qui peut diverger. Une pensée naïve consiste à utiliser , mais je ne sais pas si cela introduira un autre problème. P ( S { } ){}P(S)P(S{})
Tsuyoshi Ito
Oui, vous avez absolument raison de dire qu'en regardant l'ensemble il est déjà évident que l'espoir est perdu avant même de passer à l'exemple. Votre suggestion m'est également venue à l'esprit, mais je pense que vous vous retrouvez avec le même problème dans cet exemple, tant que la non-résiliation potentielle est modélisée par non , et si nous avons choisi ce dernier, il interfèrerait avec notre capacité à donner un sens à une boucle comme point le moins fixe de la manière habituelle. S { } { }{}P(S)S{}{}
Rob Simmons
Avez-vous regardé Dynamic Logic? La sémantique est donnée en termes de relations d'états à états, et vous pouvez utiliser la logique pour raisonner sur l'exactitude partielle et totale, c'est-à-dire les propriétés des calculs qui se terminent et que tous les calculs se terminent avec une propriété donnée.
Dave Clarke
Je n'ai pas pensé à la logique dynamique dans ce contexte, mais je vois à quel point cela pourrait être pertinent - je verrai ce que Platzer et ses élèves pensent quand je serai de retour à Pittsburgh.
Rob Simmons

Réponses:

10

Dans [dB80], l'analyse des propriétés de terminaison de la récursion par Hitchcock et Park correspond à une analyse sémantique basée sur la soi-disant interprétation Egli-Milner des relations [Egl75, Plo76], qui exprime un non-déterminisme erratique . Cette notion capture qu'une union de relations non déterministe est correcte si elle génère au moins un calcul conduisant à un résultat souhaité (même en présence d'un calcul non terminal). Cela semble correspondre à ce que vous essayez de faire.

Caractériser ensuite la signification d'une instruction comme une fonction mappant chaque état initial à un ensemble d'états non vide, contenant éventuellement , de telle sorte que est strict dans le sens où . Le choix non déterministe entre les instructions et est décrit par la fonction mappant chaque état initial à l'union des résultats individuels . Ainsi, chaque fois que ouf S σ f S f S ( ) = { } S 1 S 2 σ f S 1 ( σ ) f S 2 ( σ ) S 1SfSσfSfS()={}S1S2σfS1(σ)fS2(σ)S1S2a la possibilité non déterministe de produire un résultat indésirable, il en va de même de leur choix non déterministe. Comme l'ensemble résultant d'états finaux, on obtient dans cette analyse le soi-disant ensemble d'états d'Egli-Milner:

PE--M(S)={ sS | s est fini et non vide, ou contient}

Pourquoi les sous-ensembles infinis de ne sont-ils pas considérés comme des ensembles possibles d'états finaux dans ce modèle? Dans l'hypothèse où tous les blocs de construction de base des termes relationnels ne produisent que des ensembles finis et non vides d'états finaux possibles, un ensemble infini d'états finaux possibles ne peut être généré que lorsqu'un calcul infini est possible. Cela peut être vu comme suit. Structurez l'ensemble de tous les calculs possibles commençant dans un état donné comme un arbre avec racine et les états comme nœuds. L'ensemble des feuilles est alors exactement l'ensemble des états finaux possibles accessibles depuis , sauf pourσ 0Sσ0σ 0σ0σ0, qui peut manquer parmi les feuilles mais est représenté dans l'ensemble des états finaux par le fait qu'il existe un chemin infini dans l'arbre. Par l'hypothèse ci-dessus, et puisque seul un choix non déterministe fini est disponible, cet arbre est de ramification finie. Ainsi, il n'y a qu'un nombre fini de feuilles à une profondeur finie donnée. Par conséquent, un nombre infini d'états finaux possibles ne peut être généré qu'en présence d'un calcul infini (une application du lemme de König [Kön32]).

E - M s , t P E - M ( S )(PE--M(S),E--M) est un poset pour défini par: pour ,E--Ms,tPE--M(S)

sE--Mt=(ss{}t)(ss=t) .

Ici, peut être vu comme un espace réservé à travers lequel des ensembles plus peuvent être générés en insérant plus d'états à la place de . Par conséquent, est le plus petit élément de . De plus, le poset possède des lubrifiants pour les chaînes . De même, les fonctions strictes de à sont partiellement ordonnées par l'extension ponctuelle de . De plus, la moindre de ces fonctions estE - M{ } ( P E - M ( S ) , E - M ) ( P E - M ( S ) , E - M ) ω S { } P E --M ( S ) E - M λ σ . { } ωE--M{}(PE--M(S),E--M)(PE--M(S),E--M)ωS{}PE--M(S)E--Mλσ.{} et des chaînes de de telles fonctions existent également.ω

[dB80] JW de Bakker. Théorie mathématique de l'exactitude du programme . Prentice Hall, 1980.

[Egl75] H Egli. Un modèle mathématique pour les calculs non déterministes. Rapport technique, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen und unendlichen Graphen. Rapport technique, Leipzig, 1932.

[Plo76] GD Plotkin. Une construction de domaine de puissance. SIAM Journal on Computation , 5 (3): 452-487, 1976.

Avertissement: ceci est tiré presque mot pour mot d'un livre que j'ai co-écrit une fois:

WP de Roever et K Engelhardt. Raffinement des données: méthodes de preuve orientées modèle et leur comparaison . Cambridge University Press, 1998.

Kai
la source
4
La phrase «ceci est tiré presque verbatium d'un livre que j'ai co-écrit une fois» devrait probablement être précédée de «Extra Awesomeness:» et non «Disclaimer:» :-D. Merci, ceci est très utile.
Rob Simmons
Une façon de voir le non-déterminisme (et la façon dont je veux le voir) est qu'il s'agit d'une forme de sous - spécification - un programme avec un choix non déterministe est affiné par le programme qui prend toujours le premier choix, prend toujours le deuxième choix, ou (voir les travaux approfondis de McIver et Morgan dans ce domaine particulier) le programme qui prend un choix ou l'autre avec probabilité .5 . Ainsi, la boucle qui ne se termine pas de manière non déterministe est affinée par la boucle qui ne se termine jamais , et aussi par votre boucle de coin-flip qui se termine (avec probabilité 1)
Rob Simmons