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 científico informático y lógico británico Tony Hoare , y posteriormente refinado 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 .
Hoare triple
La característica central de la lógica de Hoare es el triple 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 es de la forma
dónde y son afirmaciones yes un comando . [nota 1] se llama la condición previa yla condición posterior : cuando se cumple la condición previa, la ejecución del comando establece la condición posterior. Las afirmaciones son fórmulas en lógica de predicados .
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 la simultaneidad , procedimientos , saltos y punteros .
Corrección parcial y total
Usando la lógica estándar de Hoare, solo se puede probar la corrección parcial , mientras que la terminación debe probarse por separado. Así, la lectura intuitiva de un triple de Hoare es: Siempre que ostenta del Estado antes de la ejecución de , luego se mantendrá después, o no termina. En el último caso, no hay "después", por lo quepuede ser cualquier declaración. De hecho, uno puede elegir ser falso para expresar eso no termina.
La corrección total también se puede demostrar con una versión extendida de la regla While. [ cita requerida ]
En su artículo de 1969, Hoare utilizó una noción más estrecha de terminación que también implicaba la ausencia de errores en tiempo de ejecución: "La falla en terminar puede deberse a un bucle infinito; o puede deberse a la violación de un límite definido por la implementación, por por ejemplo, el rango de operandos numéricos, el tamaño del almacenamiento o un límite de tiempo del sistema operativo ". [3]
Reglas
Esquema de axioma de declaración vacía
La regla de declaración vacía afirma que el declaración no cambia el estado del programa, por lo tanto, cualquier cosa que sea verdadera antes también es cierto después. [nota 2]
Esquema de 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, deja ser una aserción en la que la variable es gratis . Luego:
dónde denota la aserción en el que cada ocurrencia libre deha sido reemplazada por la expresión.
El esquema de axioma de asignación significa que la verdad de es equivalente a la verdad posterior a la asignación de . Así fueron verdadero antes de la asignación, por el axioma de asignación, entonces sería verdadero después de lo cual. Por el contrario, fueron falso (es decir verdadero) antes de la declaración de asignación, luego debe ser falso.
Ejemplos de triples válidos incluyen:
Todas las condiciones previas que no son modificadas por la expresión se pueden transferir a la condición posterior. En el primer ejemplo, asignando no cambia el hecho de que , por lo que ambas declaraciones pueden aparecer en la condición posterior. Formalmente, este resultado se obtiene aplicando el esquema de axioma con ser ( y ), cuyos rendimientos ser ( y ), que a su vez puede simplificarse a la condición previa dada .
El esquema de axioma de asignación equivale a decir que para encontrar la condición previa, primero tome la condición posterior y reemplace todas las apariciones del lado izquierdo de la asignación con el lado derecho de la asignación. Tenga cuidado de no intentar hacer esto al revés siguiendo esta forma incorrecta de pensar:; esta regla conduce a ejemplos sin sentido como:
Otra regla incorrecta que parece tentadora a primera vista es; conduce a ejemplos sin sentido como:
Mientras que una determinada poscondición determina de forma única la condición previa , lo contrario no es cierto. Por ejemplo:
- ,
- ,
- , y
son instancias válidas del esquema de 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,
está mal si y se refieren a la misma variable ( aliasing ), aunque es una instancia adecuada del esquema de axioma de asignación (con ambos y ser ).
Regla de composicion
Verificación de código de intercambio sin variables auxiliares | ||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
La regla de composición de Hoare se aplica a programas ejecutados secuencialmente y , dónde se ejecuta antes de y esta escrito (se llama condición intermedia ): [4]
Por ejemplo, considere las siguientes dos instancias del axioma de asignación:
y
Por la regla de secuenciación, se concluye:
Otro ejemplo se muestra en el cuadro de la derecha.
Regla condicional
La regla condicional establece que una poscondición común a y parte es también una condición posterior del todo declaración. En el y el parte, la condición innecesaria y negada se puede agregar a la condición previa , respectivamente. La condición,, 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
tiene el mismo efecto que una construcción de bucle de una sola vez
la regla condicional se puede derivar de las otras reglas de Hoare. De manera similar, las reglas para otras construcciones de programas derivados, como círculo, círculo, , , puede reducirse mediante la transformación del programa a las reglas del artículo original de Hoare.
Regla de consecuencia
Esta regla permite fortalecer la condición previa y / o debilitar la poscondición . Se utiliza, por ejemplo, para lograr condiciones posteriores literalmente idénticas para el y el parte.
Por ejemplo, una prueba de
necesita aplicar la regla condicional, que a su vez requiere probar
- , o simplificado
Para el parte, y
- , o simplificado
Para el parte.
Sin embargo, la regla de asignación para el parte requiere elegir como ; la aplicación de reglas, por tanto, produce
- , que es lógicamente equivalente a
- .
La regla de la consecuencia es necesaria para fortalecer la condición previa obtenido de la regla de asignación a requerido para la regla condicional.
Del mismo modo, para el parte, la regla de asignación produce
- , o equivalente
- ,
por lo tanto, la regla de la consecuencia debe aplicarse con y ser y , respectivamente, para fortalecer nuevamente la condición previa. De manera informal, el efecto de la regla de la consecuencia es "olvidar" que se conoce a la entrada de la parte, ya que la regla de asignación utilizada para el parte no necesita esa información.
Mientras gobierna
Aquí es el ciclo invariante , que debe ser preservado por el cuerpo del ciclo. Una vez finalizado el ciclo, este invariante todavía se mantiene, y además debe haber causado el final del ciclo. Como en la regla condicional, no debe tener efectos secundarios.
Por ejemplo, una prueba de
por el momento, la regla requiere probar
- , o simplificado
- ,
que se obtiene fácilmente mediante la regla de asignación. Finalmente, la poscondición se puede simplificar a .
Para otro ejemplo, la regla while se puede usar para verificar formalmente el siguiente programa extraño para calcular la raíz cuadrada exacta de un número arbitrario -incluso si es una variable entera y no es un número cuadrado:
Después de aplicar la regla while con ser , queda por probar
- ,
que se sigue de la regla de salto y la regla de consecuencia.
De hecho, el extraño programa es parcialmente correcto: si terminara, es seguro que debe haber contenido (por casualidad) el valor de raíz cuadrada de. En todos 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 puede usarse para probar la corrección total , es decir, la terminación [nota 3] así como la corrección parcial. Comúnmente, aquí se usan corchetes en lugar de llaves para indicar la noción diferente de corrección del programa.
En esta regla, además de mantener el ciclo invariante, también se prueba la terminación mediante una expresión, llamada variante de bucle , cuyo valor disminuye estrictamente con respecto a una relación bien fundada en algún conjunto de dominios durante cada iteración. Desdeestá bien fundada, una cadena estrictamente decreciente de miembros de solo puede tener una longitud finita, por lo que no puede seguir disminuyendo para siempre. (Por ejemplo, el orden habitualestá bien fundamentado en números enteros positivos , pero ni en los enteros ni en números reales positivos ; todos estos conjuntos se entienden en el sentido matemático, no en el sentido informático, todos son infinitos en particular.)
Dado el ciclo invariante , la condición debe implicar que no es un elemento mínimo de, porque de lo contrario el cuerpo no pudo disminuir más adelante, es decir, la premisa de la regla sería falsa. (Ésta es una de varias notaciones para una corrección total). [Nota 4]
Reanudando el primer ejemplo de la sección anterior , para una prueba de corrección total de
la regla while para la corrección total se puede aplicar con, por ejemplo, siendo los enteros no negativos con el orden habitual, y la expresión ser , que a su vez requiere probar
Hablando informalmente, tenemos que demostrar que la distancia disminuye en cada ciclo de bucle, mientras que siempre permanece no negativo; este proceso sólo puede continuar durante un número finito de ciclos.
El objetivo de prueba anterior se puede simplificar a
- ,
que se puede probar de la siguiente manera:
- se obtiene mediante la regla de asignación, y
- puede ser fortalecido para por la regla de la consecuencia.
Para el segundo ejemplo de la sección anterior , por supuesto, no hay expresión se puede encontrar que disminuye por el cuerpo del bucle vacío, por lo que no se puede probar la terminación.
Ver también
- Afirmación (informática)
- Comunicando procesos secuenciales
- Diseño por contrato
- Semántica denotacional
- Lógica dinámica
- Edsger W. Dijkstra
- Invariable de bucle
- Semántica del transformador de predicados
- Verificación del programa
- Cálculo de refinamiento
- Lógica de separación
- Cálculo secuencial
- Análisis de código estático
Notas
- ^ Hoare escribió originalmente "" en vez de "".
- ^ Este artículo utiliza unanotación de estilo de deducción natural para las reglas. Por ejemplo, informalmente significa "Si ambos y espera, entonces también sostiene "; y se llaman antecedentes de la regla, se llama su sucesor. Una regla sin antecedentes se llama axioma y se escribe como.
- ^ "Terminación" aquí se entiende en el sentido más amplio de que el cálculo finalmente se terminará; sí no implica que no hubo violación de límite (por ejemplo, división por cero) puede detener el programa antes de tiempo.
- ↑ El artículo de Hoare de 1969 no proporcionó una regla de corrección total; cf. su discusión en la página 579 (arriba a la izquierda). Por ejemplo, el libro de texto de Reynolds ( John C. Reynolds (2009). Teoría de los lenguajes de programación . Cambridge University Press.), Sección 3.4, p.64 da la siguiente versión de una regla de corrección total: Cuándo es una variable entera que no aparece libre en , , , o , y es una expresión entera (el nombre de las variables de Reynolds se cambió para adaptarse a la configuración de este artículo).
Referencias
- ^ a b Hoare, CAR (octubre de 1969). "Una base axiomática para la programación informática" (PDF) . Comunicaciones de la ACM . 12 (10): 576–580. doi : 10.1145 / 363235.363259 .
- ^ RW Floyd . " Asignación de significados a los programas " . Actas de los simposios de la American Mathematical Society sobre matemáticas aplicadas. Vol. 19, págs. 19–31. 1967.
- ^ p.579 arriba a la izquierda
- ^ Huth, Michael; Ryan, Mark (26 de agosto de 2004). Lógica en Ciencias de la Computación (segunda ed.). TAZA. pag. 276. ISBN 978-0521543101.
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 de KeY . Cuenta con un cálculo Hoare para un lenguaje sencillo mientras.
- Cálculo j-Algo-modul Hoare : una visualización del cálculo Hoare en el programa de visualización de algoritmos j-Algo