¿Por qué la regla de asignación es la forma en que está en Hoar Logic?

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

Pregunta

¿Por qué la regla de asignación es la forma en que está en la semántica de Hoare Logic / Axiomatic? No puedo envolver mi cabeza por qué la regla de la asignación está al revés de lo que esperaba.

Entiendo que Hoare Logic es el uso para probar proposiciones formales del estado de un programa a medida que se ejecutan los comandos. Por lo tanto, si ejecutamos el comando $$ X:= E $$ Hubiera esperado que el estado Siguiente tenga tanta sustitución ... Pero parece que la sustitución ocurre antes de ejecutamos la tarea que encuentro a Bizzare. Hubiera esperado:

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

Dado que $ P $ son declaraciones sobre el estado del programa.

Estoy seguro de que hay una buena explicación para esto y lo siento si esta es una pregunta básica, sé que debe ser. ¿Pero alguien puede explicarlo?

Pregunta de bonificación:

¿Por qué no escribimos la regla de asignación como:

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

NOTA No es lo mismo que mi sugerencia original porque tenemos el $ x $ y $ e $ intercambiado alrededor. es decir, en la condición de publicación donde, donde tenemos un $ e $ colocamos un $ x $ (que está bien Debido a que la declaración que solo ejecutamos es que $ x $ tiene el valor de $ e $ , así que deberíamos Poder reemplazar $ E $ para $ x $ en la condición de publicación si la Ayuda previa a la condición. < / p>

Publicaciones relacionadas que he leído que no han ayudado:

Apéndice:

Para los disléxicos de los Estados Unidos, en esta pregunta, esto es lo que significa la notación de sustitución:

$$ P [E / X]= P [E \ a x] $$

es. Reemplace cada aparición libre de $ x $ con expresión / término / thingie $ e $ .

¿Fue útil?

Solución

Entonces, después de leer y pensar en ello, esta es mi explicación ( gracias software gracias Fundaciones ):

La confusión clave para mí parece ser el significado de $ P [e / x] $ (reemplaza cada instancia libre de x con e). Lo que hace esto es donde vea el símbolo $ x $ Literalmente elimínelo y coloque $ e $ . p.ej. $ P [e / x]= (x + y + 1) [E / X] \ a P [E / X]= (E + Y + 1) $ Así que note cómo $ x $ desapareció literalmente de $ P $ . Entonces, lo que queremos es una vez que hacemos la asignación:

$$ x:= e $$

que la declaración es cierta si tuvimos $ x $ en lugar de $ e $ . Así que si la regla es:

$$ \ {P [E / X] \} X:= E \ {P \} $$

Luego, lo que queremos es, cuando enchufe $ x $ para $ e $ queremos el Declaración en consideración para ser verdad. Entonces, antes de comenzar el código, tenemos $ P [E / X] $ . Luego ejecutamos la tarea y todas las instancias de $ e $ desaparecen y obtenemos $ x $ 's sustituirlos. Que debe ser cierto si el código que funcionó fue asignado (desde $ x $ ahora mantenga el valor $ e $ , para que pueda eliminar $ e $ 's and Place $ x $ ).

Esa es la explicación del concepto abstracto. Permite (descaradamente) Utilice los Fundamentos de Software (SF) Ejemplo:

{{y= 1}} x ::= y {{x= 1}} En Inglés: Si nos fijamos en un estado donde el valor de Y es 1 y le asignamos a X, entonces vamos a Terminar en un estado donde X es 1. Es decir, la propiedad de ser igual a 1 se transfiere de Y a X.

Otro párrafo útil de SF:

de manera similar, en {{Y + z= 1}} x ::= y + z {{x= 1}} La misma propiedad (ser igual a una) se transfiere a X desde la expresión y + z en el lado derecho de la asignación. Más generalmente, si A es alguna expresión aritmética, entonces {{a= 1}} x ::= a {{x= 1}} es un triple valido de Hoare.

Anexo de la gran observación de los comentarios:

Es importante reconocer que la regla { PAG [ mi / X ] } X := mi { PAG } permite tanto la expresión mi y la variable X Para ocurrir en la postcondición. En otras palabras, la regla de inferencia le permite deducir una postcondencia en la que cualquier subconjunto de las ocurrencias de mi En la condición previa ha sido reemplazada por X , incluyendo ninguno de ellos. Además, le permite deducir todas estas diferentes postconditiones simultáneamente.

Responder a Bonus ¿Por qué es

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

mejor que

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

Además del punto sutil de reemplazar X con expresiones que pueden ser invisibles (por ejemplo, E= 0, deberíamos reemplazar $ 0 $ con un número infinito de $ x $ 's? ¿Qué pasa si los ceros no están allí ... las reglas deben ser sintácticas, pero creo que es mejor evitar tales confusiones), creo que esta es la razón: < / p>

Lo que la regla de la asignación debe capturar es que estamos asignando la expresión E a la variable x. Por lo tanto, solo X debe ser "reemplazado" por e. Intuitivamente, en el código (o más precisamente el estado del programa $ \ sigma $ ) cuando X comienza a mantener el valor E, no significa aleatoriamente que en todas partes donde Puede haber una E que se convierta en X después de ejecutar la asignación $ x:= e $ . De hecho, lo que significa es que ahora en la condición de publicación tenemos X's. Ahora esos X's Si no tuvimos la tarea deberíamos tener el valor de $ e $ i.e. Solo "deshacer" el reemplazo / asignación se realizó el comando de asignación. No todas las demás expresión aleatoria e. En resumen, la única forma de saber dónde colocar los E MI correctos está comenzando en la condición de poste después de que se haya realizado la asignación, luego comenzando desde allí. Si lo hacemos hacia atrás, podríamos estar reemplazando E's, no queríamos reemplazar (incluso si probablemente fueran ciertos, lo que supongo que deberían decir que no estamos diciendo que X tiene el valor E después de asignar E a X).

Otros consejos

Supongamos que estamos ejecutando el programa x := e, y deje que $ \ sigma $ sea el estado inicial, y $ \ sigma ' $ ser el estado final.

La intuición crucial aquí es: el valor de $ x $ en el estado Final State $ \ SIGMA '$ es lo mismo que el valor de la expresión $ e $ en el estado inicial $ \ Sigma $ . De hecho, este último es el valor que asignamos a $ x $ con el comando x := e.

Por lo tanto, si $ P (-) $ es una propiedad en valores, la fórmula $ p (\ mbox { $ x $ -in-the-Final-State}) $ es equivalente a $ P (\ mbox {$ e $ -in-the-inicial-estado}) $ . En otras palabras, $ P (x) $ en el postcondition (en estado $ \ sigma ' $ ) es realmente equivalente a $ P (e) $ en la prededition (en estado $ \ sigma $ ).

Uso de la sustitución es solo una forma más formal de considerar la poscondición como una "fórmula que depende de $ x $ ", es decir, como $ P (x) $ y luego requieren $ P (e) $ como condición previa.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top