Perché la regola di assegnazione è il modo in cui è in Hoare Logic?

cs.stackexchange https://cs.stackexchange.com/questions/118322

Domanda

Perché la regola di assegnazione è il modo in cui è in Hoare Logic / Axiomatic Semantics? Non riesco ad avvolgermi la testa perché la regola di assegnazione è all'indietro da quello che mi aspettavo.

Compreso Hoare Logic è l'uso per dimostrare proposizioni formali dello stato di un programma poiché vengono eseguiti comandi. Quindi, se eseguiamo il comando $$ x:= E $$ mi sarei aspettato che lo stato next ha tale sostituzione ... Ma sembra che la sostituzione accada prima eseguiamo l'incarico che trovo Bizzare. Mi sarei aspettato:

$$ \ {p \} x:= e \ {P [e / x] \} $$

Dato che $ p $ sono affermazioni sullo stato del programma.

Sono sicuro che c'è una buona spiegazione per questo e scusa se questa è una domanda fondamentale, so che deve essere. Ma qualcuno può spiegarmelo?

.

Domanda bonus:

Perché non scriviamo la regola di assegnazione come:

$$ \ {q \} x:= e \ {q [x / e] \} $$

nota non è la stessa del mio suggerimento originale perché abbiamo la $ x $ e $ e $ scambiato intorno. cioè nella condizione postale ovunque abbiamo una classe $ E $ Posizioniamo una classe $ x $ (che va bene Poiché la dichiarazione che eseguiamo semplicemente è quella $ x $ contiene il valore di $ e $ , quindi dovremmo essere in grado di sostituire $ e $ per $ x $ nella condizione post se la condizione predica la condizione. < / P >.

.

Messaggi correlati che ho letto che non hanno aiutato:

.

Appendice:

Per la dislessia degli Stati Uniti, in questa domanda questo è ciò che la notazione di sostituzione significa:

$$ P [E / x]= P [E \ to x] $$

I.e. Sostituisci ogni evento GRATUITO di $ x $ con espressione / termine / thingie $ e $ .

È stato utile?

Soluzione

Quindi dopo aver letto e pensarci di più questa è la mia spiegazione ( grazie Software Fondazioni ):

La confusione chiave per me sembra essere il significato di $ P [E / x] $ (sostituisce ogni istanza gratuita di X con E). Cosa fa dove si vede il simbolo $ x $ letteralmente rimuoverlo e posizionare $ e $ . per esempio. $ P [E / X]= (X + Y + 1) [E / X] \ a P [E / X]= (E + Y + 1) $ Avviso come $ x $ Letteralmente scomparvero da $ p $ . Quindi quello che vogliamo è una volta che facciamo il compito:

$$ x:= e $$

che la dichiarazione è vera se avessimo $ x $ invece di $ e $ . Quindi se la regola è:

$$ \ {p [e / x] \} x:= e \ {p \} $$

Allora ciò che vogliamo è, quando colleghiamo $ x $ per $ e $ Vogliamo il dichiarazione in considerazione per essere vero. Quindi, prima di avviare il codice abbiamo $ P [e / x] $ . Quindi eseguiamo l'assegnazione e tutte le istanze di $ e $ scomparire e otteniamo $ x $ sostituirli. Quella deve essere true se il codice che correva è stato assegnato (poiché $ x $ ora tieni il valore $ e $ , così puoi rimuovere $ e $ 's e posizionare $ x $ ).

è la spiegazione del concetto astratto. Lascia (spudoratamente) Utilizzare le basi software (SF) Esempio:

.

{{y= 1}} x ::= y {{x= 1}} in inglese: se iniziamo in uno stato in cui il valore di Y è 1 e assegniamo Y a X, allora lo faremo Finitura in uno stato in cui X è 1. Quello è, la proprietà di essere uguale a 1 viene trasferita da Y a X.

Un altro utile paragrafo da SF:

.

Allo stesso modo, in {{Y + z= 1}} x ::= y + z {{x= 1}} La stessa proprietà (essere uguale a una) viene trasferita a X dall'espressione Y + Z sul lato destro del compito. Più in generale, se A è un'espressione aritmetica, allora {{A= 1}} X ::= A {{X= 1}} è un triplo di hoare valido.

.

Addendum dalla grande osservazione del commento:

.

È importante riconoscere che la regola { P. [ E. / X ] } X :=.. E. { P. } consente sia l'espressione E. e la variabile X si verificano nella postcondition. In altre parole, la regola dell'inferenza consente di dedurre una postcondition in cui qualsiasi sottoinsieme delle occorrenze di E. nella precondizione è stato sostituito con X , inclusi nessuno di loro. Inoltre, consente di dedurre tutte queste diverse postcondizioni contemporaneamente.

.

Rispondi a Bonus Perché

1) $ \ {p [e / x] \} x:= e \ {p \} $

Meglio di

2) $ \ {q \} x:= e \ {q [x / e] \} $ :

oltre al punto sottile di sostituzione x con espressioni che potrebbero essere invisibili (ad es. E= 0, dovremmo sostituire $ 0 $ con un numero infinito di $ x $ 'S? Cosa succede se gli zeri non ci sono ... Le regole dovrebbero essere sintattiche ma penso che sia meglio evitare tali confusioni), penso che questa sia la ragione: < / P >.

.

Qual è la regola di assegnazione della regola è che stiamo assegnando l'espressione e alla variabile x. Quindi, solo x dovrebbe essere "sostituito" da e. Intuitivamente, nel codice (o più precisamente lo stato del programma $ \ sigma $ ) Quando X inizia a tenere il valore E, non significa in modo casuale ovunque Potrebbe esserci un e diventa x dopo aver eseguito l'assegnazione $ x:= E $ . In realtà ciò che significa è che ora nella condizione post abbiamo X's. Ora quelle x se non avessimo il compito non avremmo dovuto avere il valore di $ e $ I.e. Ci "annulla" solo il comando sostitutivo / assegnazione del comando di assegnazione. Non tutte le altre espressioni casuali e. In breve, l'unico modo per sapere dove posizionare l'E corretto è iniziando nella condizione post dopo che l'incarico è stato fatto, quindi iniziando da lì posto E. Se lo facciamo all'indietro, potremmo sostituire E 'che non volevamo sostituire (anche se erano probabilmente vere, che immagino che dovrebbero dal momento che dovremmo dire x tiene il valore E dopo aver assegnato E a X).

Altri suggerimenti

Supponiamo che stiamo eseguendo il programma x := e e lascia che $ \ sigma $ essere lo stato iniziale e $ \ sigma ' $ essere lo stato finale.

L'intuizione cruciale qui è: il valore della $ x $ nella finale stato $ \ Sigma '$ è uguale al valore dell'espressione $ e $ nella iniziale stato $ \ Sigma $ . Infatti, quest'ultimo è il valore che assegniamo a $ x $ con il comando x := e.

quindi, se $ P (-) $ è una proprietà su valori, la formula $ P (\ MBOX { $ x $ -in-the-final-state}) $ equivalente a $ p (\ mbox {$ e $ -in-the-statel-state}) $ . In altre parole $ p (x) $ in postcondition (in stato $ \ Sigma ' $ ) è davvero equivalente a $ p (e) $ nel preliminare (in stato $ \ Sigma $ ).

L'utilizzo della sostituzione è solo un modo più formale per considerare la postcondition come "formula che dipende da $ x $ ", cioè come $ P (x) $ , quindi richiede $ P (e) $ come precondizione.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top