Lógica larga

Reglas para verificar la corrección del programa informático.

La lógica de Hoare (también conocida como lógica de Floyd-Hoare o reglas de Hoare ) es un sistema formal con un conjunto de reglas lógicas para razonar rigurosamente sobre la corrección de los programas de computadora . Fue propuesto en 1969 por el informático y lógico británico Tony Hoare , y posteriormente perfeccionado por Hoare y otros investigadores. ^[1] Las ideas originales fueron sembradas por el trabajo de Robert W. Floyd , quien había publicado un sistema similar ^[2] para diagramas de flujo .

triple ronco

La característica central de la lógica de Hoare es la tripleta de Hoare . Un triple describe cómo la ejecución de un fragmento de código cambia el estado del cálculo. Un triple de Hoare tiene la forma

${\displaystyle \{P\}C\{Q\}}$

donde y son afirmaciones y es un comando . ^{[nota 1]} se denomina condición previa y poscondición : cuando se cumple la condición previa, la ejecución del comando establece la poscondición . Las afirmaciones son fórmulas en lógica de predicados . ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle C}$ ${\displaystyle P}$ ${\displaystyle Q}$

La lógica de Hoare proporciona axiomas y reglas de inferencia para todas las construcciones de un lenguaje de programación imperativo simple . Además de las reglas para el lenguaje simple en el artículo original de Hoare, desde entonces Hoare y muchos otros investigadores han desarrollado reglas para otras construcciones del lenguaje. Hay reglas para concurrencia , procedimientos , saltos y punteros .

Corrección parcial y total.

Utilizando la lógica estándar de Hoare, sólo se puede demostrar una corrección parcial . La corrección total requiere además la terminación , que se puede probar por separado o con una versión ampliada de la regla While. ^[3] Así, la lectura intuitiva de una tripleta de Hoare es: Siempre que se mantenga el estado antes de la ejecución de , se mantendrá después o no terminará. En el último caso, no hay "después", por lo que puede haber cualquier declaración. En efecto, uno puede optar por ser falso para expresar algo que no termina. ${\displaystyle P}$ ${\displaystyle C}$ ${\displaystyle Q}$ ${\displaystyle C}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle C}$

"Terminación" aquí y en el resto de este artículo se entiende en el sentido más amplio de que el cálculo eventualmente terminará, es decir, implica la ausencia de bucles infinitos; no implica la ausencia de violaciones de los límites de implementación (por ejemplo, división por cero) que detengan el programa prematuramente. En su artículo de 1969, Hoare utilizó una noción más estrecha de terminación que también implicaba la ausencia de violaciones de los límites de implementación, y expresó su preferencia por la noción más amplia de terminación, ya que mantiene las afirmaciones independientes de la implementación: ^[4]

Otra deficiencia de los axiomas y reglas citados anteriormente es que no proporcionan ninguna base para demostrar que un programa termina exitosamente. La imposibilidad de terminar puede deberse a un bucle infinito; o puede deberse a una violación de un límite definido por la implementación, por ejemplo, el rango de operandos numéricos, el tamaño del almacenamiento o un límite de tiempo del sistema operativo. Por lo tanto, la notación " " debe interpretarse "siempre que el programa finalice exitosamente, las propiedades de sus resultados se describen mediante ". Es bastante fácil adaptar los axiomas para que no puedan usarse para predecir los “resultados” de programas que no terminan; pero el uso real de los axiomas dependería ahora del conocimiento de muchas características dependientes de la implementación, por ejemplo, el tamaño y la velocidad de la computadora, el rango de números y la elección de la técnica de desbordamiento. Aparte de las pruebas de cómo evitar bucles infinitos, probablemente sea mejor probar la corrección "condicional" de un programa y confiar en una implementación para dar una advertencia si ha tenido que abandonar la ejecución del programa como resultado de la violación de una límite de implementación. ${\displaystyle P\{Q\}R}$ ${\displaystyle R}$

Normas

Esquema de axioma de declaración vacía

La regla de la declaración vacía afirma que la declaración de salto no cambia el estado del programa, por lo tanto, todo lo que sea cierto antes del salto también lo será después. ^{[nota 2]}

${\displaystyle {\dfrac {}{\{P\}{\texttt {skip}}\{P\}}}}$

Esquema del axioma de asignación

El axioma de asignación establece que, después de la asignación, cualquier predicado que antes era verdadero para el lado derecho de la asignación ahora es válido para la variable. Formalmente, sea P una afirmación en la que la variable x es libre . Entonces:

${\displaystyle {\dfrac {}{\{P[E/x]\}x:=E\{P\}}}}$

donde denota la afirmación P en la que cada aparición libre de x ha sido reemplazada por la expresión E . ${\displaystyle P[E/x]}$

El esquema del axioma de asignación significa que la verdad de es equivalente a la verdad posterior a la asignación de P. Por lo tanto, si fueran verdaderas antes de la asignación, según el axioma de asignación, entonces P sería verdadera después de la cual. Por el contrario, si fuera falso (es decir, verdadero) antes de la declaración de asignación, P debe ser falso después. ${\displaystyle P[E/x]}$ ${\displaystyle P[E/x]}$ ${\displaystyle P[E/x]}$ ${\displaystyle \neg P[E/x]}$

Ejemplos de triples válidos incluyen:

• ${\displaystyle \{x+1=43\}y:=x+1\{y=43\}}$
• ${\displaystyle \{x+1\leq N\}x:=x+1\{x\leq N\}}$

Todas las condiciones previas que no sean modificadas por la expresión se pueden trasladar a la condición posterior. En el primer ejemplo, la asignación no cambia el hecho de que , por lo que ambas declaraciones pueden aparecer en la poscondición. Formalmente, este resultado se obtiene aplicando el esquema del axioma donde P es ( y ), lo que produce ser ( y ), que a su vez puede simplificarse a la condición previa dada . ${\displaystyle y:=x+1}$ ${\displaystyle x+1=43}$ ${\displaystyle y=43}$ ${\displaystyle x+1=43}$ ${\displaystyle P[(x+1)/y]}$ ${\displaystyle x+1=43}$ ${\displaystyle x+1=43}$ ${\displaystyle x+1=43}$

El esquema del axioma de asignación equivale a decir que para encontrar la condición previa, primero se toma la condición posterior y se reemplazan todas las apariciones del lado izquierdo de la tarea con el lado derecho de la tarea. Tenga cuidado de no intentar hacer esto al revés siguiendo esta forma incorrecta de pensar: ; esta regla lleva a ejemplos sin sentido como: ${\displaystyle \{P\}x:=E\{P[E/x]\}}$

${\displaystyle \{x=5\}x:=3\{3=5\}}$

Otra regla incorrecta que parece tentadora a primera vista es ; conduce a ejemplos sin sentido como: ${\displaystyle \{P\}x:=E\{P\wedge x=E\}}$

${\displaystyle \{x=5\}x:=x+1\{x=5\wedge x=x+1\}}$

Si bien una poscondición determinada P determina de forma única la precondición , lo contrario no es cierto. Por ejemplo: ${\displaystyle P[E/x]}$

• ${\displaystyle \{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq x\wedge x\leq 9\}}$,
• ${\displaystyle \{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq x\wedge y\cdot y\leq 9\}}$,
• ${\displaystyle \{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq y\cdot y\wedge x\leq 9\}}$, y
• ${\displaystyle \{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq y\cdot y\wedge y\cdot y\leq 9\}}$

son ejemplos válidos del esquema del axioma de asignación.

El axioma de asignación propuesto por Hoare no se aplica cuando más de un nombre puede referirse al mismo valor almacenado. Por ejemplo,

${\displaystyle \{y=3\}x:=2\{y=3\}}$

es incorrecto si x e y se refieren a la misma variable ( aliasing ), aunque es una instancia adecuada del esquema del axioma de asignación (con ambos y siendo ). ${\displaystyle \{P\}}$ ${\displaystyle \{P[2/x]\}}$ ${\displaystyle \{y=3\}}$

Regla de composición

La regla de composición de Hoare se aplica a los programas ejecutados secuencialmente S y T , donde S se ejecuta antes de T y se escribe ( Q se llama condición intermedia ): ^[5] ${\displaystyle S;T}$

${\displaystyle {\dfrac {\{P\}S\{Q\}\quad ,\quad \{Q\}T\{R\}}{\{P\}S;T\{R\}}}}$

Por ejemplo, considere los siguientes dos casos del axioma de asignación:

${\displaystyle \{x+1=43\}y:=x+1\{y=43\}}$

y

${\displaystyle \{y=43\}z:=y\{z=43\}}$

Por la regla de secuenciación se concluye:

${\displaystyle \{x+1=43\}y:=x+1;z:=y\{z=43\}}$

Otro ejemplo se muestra en el cuadro de la derecha.

regla condicional

${\displaystyle {\dfrac {\{B\wedge P\}S\{Q\}\quad ,\quad \{\neg B\wedge P\}T\{Q\}}{\{P\}{\texttt {if}}\ B\ {\texttt {then}}\ S\ {\texttt {else}}\ T\ {\texttt {endif}}\{Q\}}}}$

La regla condicional establece que una poscondición Q común a la parte then y else también es una poscondición del todo if...endif . ^[6] En la parte entonces y en la otra parte, la condición B no negada y negada se puede agregar a la condición previa P , respectivamente. La condición B no debe tener efectos secundarios. En la siguiente sección se ofrece un ejemplo.

Esta regla no estaba contenida en la publicación original de Hoare. ^[1] Sin embargo, desde una declaración

${\displaystyle {\texttt {if}}\ B\ {\texttt {then}}\ S\ {\texttt {else}}\ T\ {\texttt {endif}}}$

tiene el mismo efecto que una construcción de bucle de una sola vez

${\displaystyle {\texttt {bool}}\ b:={\texttt {true}};{\texttt {while}}\ B\wedge b\ {\texttt {do}}\ S;b:={\texttt {false}}\ {\texttt {done}};b:={\texttt {true}};{\texttt {while}}\ \neg B\wedge b\ {\texttt {do}}\ T;b:={\texttt {false}}\ {\texttt {done}}}$

la regla condicional se puede derivar de las otras reglas de Hoare. De manera similar, las reglas para otras construcciones de programas derivados, como for loop, do...until loop, switch , break , continue pueden reducirse mediante la transformación del programa a las reglas del artículo original de Hoare.

regla de consecuencia

${\displaystyle {\dfrac {P_{1}\rightarrow P_{2}\quad ,\quad \{P_{2}\}S\{Q_{2}\}\quad ,\quad Q_{2}\rightarrow Q_{1}}{\{P_{1}\}S\{Q_{1}\}}}}$

Esta regla permite fortalecer la precondición y/o debilitar la poscondición . Se utiliza, por ejemplo, para lograr condiciones posteriores literalmente idénticas para la parte then y else . ${\displaystyle P_{2}}$ ${\displaystyle Q_{2}}$

Por ejemplo, una prueba de

${\displaystyle \{0\leq x\leq 15\}{\texttt {if}}\ x<15\ {\texttt {then}}\ x:=x+1\ {\texttt {else}}\ x:=0\ {\texttt {endif}}\{0\leq x\leq 15\}}$

necesita aplicar la regla condicional, lo que a su vez requiere demostrar

${\displaystyle \{0\leq x\leq 15\wedge x<15\}x:=x+1\{0\leq x\leq 15\}}$, o simplificado

${\displaystyle \{0\leq x<15\}x:=x+1\{0\leq x\leq 15\}}$

para la parte entonces , y

${\displaystyle \{0\leq x\leq 15\wedge x\geq 15\}x:=0\{0\leq x\leq 15\}}$, o simplificado

${\displaystyle \{x=15\}x:=0\{0\leq x\leq 15\}}$

por la otra parte.

Sin embargo, la regla de asignación para la parte entonces requiere elegir P como ; la aplicación de la regla por lo tanto produce ${\displaystyle 0\leq x\leq 15}$

${\displaystyle \{0\leq x+1\leq 15\}x:=x+1\{0\leq x\leq 15\}}$, que es lógicamente equivalente a

${\displaystyle \{-1\leq x<15\}x:=x+1\{0\leq x\leq 15\}}$.

La regla de consecuencia es necesaria para fortalecer la condición previa obtenida de la regla de asignación a lo requerido por la regla condicional. ${\displaystyle \{-1\leq x<15\}}$ ${\displaystyle \{0\leq x<15\}}$

De manera similar, para la otra parte, la regla de asignación produce

${\displaystyle \{0\leq 0\leq 15\}x:=0\{0\leq x\leq 15\}}$, o equivalente

${\displaystyle \{{\texttt {true}}\}x:=0\{0\leq x\leq 15\}}$,

por lo tanto, la regla de la consecuencia debe aplicarse con y siendo y , respectivamente, para fortalecer nuevamente la condición previa. Informalmente, el efecto de la regla de consecuencia es "olvidar" lo que se conoce en la entrada de la parte else , ya que la regla de asignación utilizada para la parte else no necesita esa información. ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle \{x=15\}}$ ${\displaystyle \{{\texttt {true}}\}}$ ${\displaystyle \{x=15\}}$

mientras gobierna

${\displaystyle {\dfrac {\{P\wedge B\}S\{P\}}{\{P\}{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}\{\neg B\wedge P\}}}}$

Aquí P es el invariante del bucle , que debe ser preservado por el cuerpo del bucle S. Una vez finalizado el ciclo, esta P invariante aún se mantiene y, además, debe haber causado que el ciclo termine. Como en la regla condicional, B no debe tener efectos secundarios. ${\displaystyle \neg B}$

Por ejemplo, una prueba de

${\displaystyle \{x\leq 10\}{\texttt {while}}\ x<10\ {\texttt {do}}\ x:=x+1\ {\texttt {done}}\{\neg x<10\wedge x\leq 10\}}$

por el momento la regla requiere probar

${\displaystyle \{x\leq 10\wedge x<10\}x:=x+1\{x\leq 10\}}$, o simplificado

${\displaystyle \{x<10\}x:=x+1\{x\leq 10\}}$,

que se obtiene fácilmente mediante la regla de asignación. Finalmente, la poscondición se puede simplificar a . ${\displaystyle \{\neg x<10\wedge x\leq 10\}}$ ${\displaystyle \{x=10\}}$

Para otro ejemplo, la regla while se puede utilizar para verificar formalmente el siguiente extraño programa para calcular la raíz cuadrada exacta x de un número arbitrario a , incluso si x es una variable entera y a no es un número cuadrado:

${\displaystyle \{{\texttt {true}}\}{\texttt {while}}\ x\cdot x\neq a\ {\texttt {do}}\ {\texttt {skip}}\ {\texttt {done}}\{x\cdot x=a\wedge {\texttt {true}}\}}$

Después de aplicar la regla while siendo P verdadera , queda por demostrar

${\displaystyle \{{\texttt {true}}\wedge x\cdot x\neq a\}{\texttt {skip}}\{{\texttt {true}}\}}$,

que se sigue de la regla de omisión y de la regla de consecuencia.

De hecho, el extraño programa tiene parte de razón: si termina, es seguro que x debe haber contenido (por casualidad) el valor de la raíz cuadrada de a . En los demás casos no terminará; por lo tanto no es del todo correcto.

Mientras que la regla para la corrección total

Si la regla while ordinaria anterior se reemplaza por la siguiente, el cálculo de Hoare también se puede utilizar para demostrar la corrección total , es decir, la terminación y la corrección parcial. Comúnmente, aquí se utilizan corchetes en lugar de llaves para indicar la noción diferente de corrección del programa.

${\displaystyle {\dfrac {<\ {\text{is a well-founded ordering on the set}}\ D\quad ,\quad [P\wedge B\wedge t\in D\wedge t=z]S[P\wedge t\in D\wedge t<z]}{[P\wedge t\in D]{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}[\neg B\wedge P\wedge t\in D]}}}$

En esta regla, además de mantener el bucle invariante, también se prueba la terminación mediante una expresión t , llamada variante del bucle , cuyo valor disminuye estrictamente con respecto a una relación bien fundada < en algún conjunto de dominios D durante cada iteración. Dado que < está bien fundamentado, una cadena estrictamente decreciente de miembros de D sólo puede tener una longitud finita, por lo que t no puede seguir disminuyendo eternamente. (Por ejemplo, el orden habitual < está bien fundamentado en números enteros positivos , pero no en números enteros ni en números reales positivos ; todos estos conjuntos están pensados ​​en el sentido matemático, no en el computacional, todos son infinitos en particular.) ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {R} ^{+}}$

Dado el invariante del bucle P , la condición B debe implicar que t no es un elemento mínimo de D , porque de lo contrario el cuerpo S no podría disminuir t más, es decir, la premisa de la regla sería falsa. (Esta es una de varias notaciones para una total corrección). ^{[nota 3]}

Retomando el primer ejemplo de la sección anterior, para una prueba de total corrección de

${\displaystyle [x\leq 10]{\texttt {while}}\ x<10\ {\texttt {do}}\ x:=x+1\ {\texttt {done}}[\neg x<10\wedge x\leq 10]}$

se puede aplicar la regla while para la corrección total, siendo, por ejemplo, D los números enteros no negativos con el orden habitual y siendo t la expresión , lo que a su vez requiere demostrar ${\displaystyle 10-x}$

${\displaystyle [x\leq 10\wedge x<10\wedge 10-x\geq 0\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x\geq 0\wedge 10-x<z]}$

Hablando informalmente, tenemos que demostrar que la distancia disminuye en cada ciclo del bucle, mientras que siempre permanece no negativa; este proceso sólo puede continuar durante un número finito de ciclos. ${\displaystyle 10-x}$

El objetivo de prueba anterior se puede simplificar a

${\displaystyle [x<10\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x<z]}$,

lo cual se puede demostrar de la siguiente manera:

${\displaystyle [x+1\leq 10\wedge 10-x-1<z]x:=x+1[x\leq 10\wedge 10-x<z]}$se obtiene mediante la regla de asignación, y

${\displaystyle [x+1\leq 10\wedge 10-x-1<z]}$puede reforzarse mediante la regla de las consecuencias. ${\displaystyle [x<10\wedge 10-x=z]}$

Para el segundo ejemplo de la sección anterior, por supuesto, no se puede encontrar ninguna expresión t que sea disminuida por el cuerpo del bucle vacío, por lo que no se puede probar la terminación.

Ver también

• Afirmación (desarrollo de software)
• Semántica denotacional
• Diseño por contrato
• Lógica dinámica
• Verificación formal
• Bucle invariante
• Semántica del transformador de predicados
• Análisis estático del programa.

Notas

1. Hoare escribió originalmente " " en lugar de " ". ${\displaystyle P\{C\}Q}$ ${\displaystyle \{P\}C\{Q\}}$
2. Este artículo utiliza una notación de estilo de deducción natural para las reglas. Por ejemplo, informalmente significa "Si tanto α como β se cumplen, entonces también se cumple φ "; α y β se llaman antecedentes de la regla, φ se llama su sucesor. Una regla sin antecedentes se llama axioma y se escribe como . ${\displaystyle {\dfrac {\alpha ,\beta }{\phi }}}$ ${\displaystyle {\dfrac {}{\quad \phi \quad }}}$
3. El artículo de Hoare de 1969 no proporcionó una regla de corrección total; cf. su discusión en la p.579 (arriba a la izquierda). Por ejemplo, el libro de texto de Reynolds ^[3] ofrece la siguiente versión de una regla de corrección total: cuando z es una variable entera que no ocurre libremente en P , B , S o t , y t es una expresión entera (variables de Reynolds renombrado para ajustarse a la configuración de este artículo). ${\displaystyle {\dfrac {P\wedge B\rightarrow 0\leq t\quad ,\quad [P\wedge B\wedge t=z]S[P\wedge t<z]}{[P]{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}[P\wedge \neg B]}}}$

Referencias

1. Hoare, CAR (octubre de 1969). "Una base axiomática para la programación informática". Comunicaciones de la ACM . 12 (10): 576–580. doi : 10.1145/363235.363259 . S2CID  207726175.
2. RW Floyd . "Asignación de significados a los programas". Actas de los simposios de la Sociedad Estadounidense de Matemáticas sobre Matemáticas Aplicadas. vol. 19, págs. 19-31. 1967.
3. John C. Reynolds (2009). Teorías de los lenguajes de programación . Prensa de la Universidad de Cambridge.) Aquí: Secc. 3.4, pág. 64.
4. Hoare (1969), páginas 578-579
5. Huth, Michael; Ryan, Mark (26 de agosto de 2004). Lógica en Informática (segunda ed.). TAZA. pag. 276.ISBN​ 978-0521543101.
6. Apto, Krzysztof R.; Olderog, Ernst-Rüdiger (diciembre de 2019). "Cincuenta años de la lógica de Hoare". Aspectos formales de la informática . 31 (6): 759. doi :10.1007/s00165-019-00501-3. S2CID  102351597.

Otras lecturas

• Robert D. Tennent. Especificación de software (un libro de texto que incluye una introducción a la lógica de Hoare, escrito en 2002) ISBN 0-521-00401-2 

enlaces externos

• KeY-Hoare es un sistema de verificación semiautomático construido sobre el demostrador del teorema KeY . Cuenta con un cálculo de Hoare para un lenguaje simple.
• Módulo j-Algo Hoare Calculus (j-Algo en GitHub , j-Algo en SourceForge ): una visualización del cálculo de Hoare en el programa de visualización de algoritmos j-Algo.