ACL2

ACL2 es, a la vez, un lenguaje de programación, una lógica matemática para especificar y demostrar formalmente propiedades de los programas escritos en dicho lenguaje, y un demostrador automático de teoremas que asiste al usuario en dicha tarea. ACL2 es la versión industrial del demostrador NQTHM de R. Boyer y J S. Moore. En la actualidad está desarrollado por J S. Moore y M. Kaufmann en la Universidad de Texas en Austin. El nombre ACL2 es una abreviatura de A Computational Logic for an Applicative Common LISP.^[1]

El lenguaje de programación ACL2 es un subconjunto aplicativa de Common LISP. ACL2 es un lenguaje sin tipos debido a que todas las funciones de ACL2 son totales –es decir, toda función asocia a cada valor del universo de ACL2 otro valor de ese universo. Los programas escritos en ACL2 pueden ser ejecutados en Common Lisp directamente. El propio ACL2 está desarrollado usando su mismo lenguaje aplicativo.

Una característica importante de ACL2 es que se usa el mismo lenguaje tanto para la implementación de los programas como para la especificación de sus propiedades. La lógica de ACL2 es un subconjunto de la lógica de primer orden. Sus fórmulas no tienen cuantificadores y las variables de una fórmula se consideran (implícitamente) universalmente cuantificadas. La teoría de base de ACL2 axiomatiza la semántica de su lenguaje de programación y de sus funciones predefinidas, tal y como se describen en el estándar Common Lisp. Cuando las definiciones del usuario satisfacen un cierto principio de definición extienden la teoría con el correspondiente axioma de definición. Grosso modo, el principio de definición garantiza que la función definida termina para todas las entradas posibles, manteniendo así la consistencia lógica de la teoría.

El demostrador de ACL2 puede considerarse como un asistente para la demostración de teoremas en la lógica de ACL2. El motor de demostración de ACL2 está basado principalmente en la reescritura de términos y en la automatización del principio de inducción. Aunque en principio ACL2 puede ser considerado un demostrador automático (una vez introducida una conjetura, procede de manera automática en su intento de demostración), el sistema es interactivo en un sentido más profundo. El papel del usuario en una formalización típica con ACL2 consiste en: a) definir las funciones que implementan el sistema que se quiere verificar, b) escribir la especificación del mismo, expresando las propiedades formales que se desean verificar y c) guiar al demostrador hacia una demostración automática de dicha especificación. La manera principal mediante la cual el usuario guía al demostrador consiste en la demostración de lemas previos que se incluyen en el sistema como reglas de reescritura y que son usados en la demostración de posteriores resultados. Los lemas específicos necesarios para cada demostración pueden venir sugeridos de una demostración (manual) preconcebida o bien, a más bajo nivel, de la inspección de la salida generada por un intento de demostración automática fallido.

El objetivo de los creadores de ACL2 fue realizar una versión del demostrador NQTHM de Boyer-Moore que pudiera ser utilizado para aplicaciones de escala industrial. Por ese objetivo, ACL2 contiene muchas características que permiten el desarrollo limpio de teorías matemáticas y computacionales. Además, ACL2 obtiene eficiencia gracias a que está escrito en Common LISP. Así, la misma especificación que es la base para una verificación formal puede ser compilada y ejecutada en código nativo.

La principal aplicación de ACL2 se encuentra en la verificación formal de sistemas hardware cuya seguridad es crítica. Dichos sistemas son modelados en el lenguaje de programación y las propiedades que aseguran su corrección son formalmente verificadas. El hecho de que el modelo pueda ser ejecutado de manera eficiente permite además que pueda ser usado como un simulador del sistema modelado.^[2]

En el año 2005, la ACM concedió el premio de software al demostrador de teoremas de Boyer y Moore (lo que incluye tanto a NQTHM como a ACL2). Literalmente, el premio se concede a R. Boyer, M. Kaufmann y J S. Moore por ser precursores y autores "del más efectivo demostrador de teoremas como una herramienta de métodos formales para la verificación de hardware y software cuya seguridad es crítica".^[3]

Sistemas de reescritura de ACL2

La lógica ecuacional se formaliza en ACL2, un lenguaje de programación y de lógica matemática utilizado para la demostración formal de teoremas.

Su concepto de consecuencia lógica se representa mediante un conjunto de axiomas ecuacionales que puede ser descrito mediante una relación de equivalencia. Esta relación procede del conjunto de términos de primer orden, es decir, mediante axiomas reemplazando iguales por iguales (proposiciones que se asumen como verdaderas sin necesidad de una demostración previa). Lo anteriormente dicho es como se representa en ACL2 la teoría ecuacional.

Se dice sistema de reescritura al conjunto de ecuaciones orientadas de derecha a izquierda y para conseguir la reducción asociada a este tipo de sistemas se emplea la noetherianidad y un algoritmo de cálculo de formas normales. Un sistema de reescritura concluye en estudiar un conjunto finito de pares llamados pares críticos.

Tipos de datos en ACL2

Existen diferentes tipos de objetos en ACL2:

Tipos de objetos
Objeto	Valor asociado
Números	7, -5, 2/5, #c(2 1).
Caracteres	#\a, #\Space.
Cadenas de caracteres	"Buenas" "Tardes"
Símbolos	t, nil, x, NWM::a.
Pares punteados	(1 . 2), (i j k).

En cuanto al manejo de los diferentes tipos de números en ACL2:

Los números racionales se escriben como fracción de números enteros.
En ACL2, los símbolos están formados por dos cadenas de caracteres: su nombre de paquete y su nombre de símbolo.
- Por ejemplo, el símbolo cuyo nombre de paquete es NWM y cuyo nombre de símbolo es a, se escribe NWM::a

Teorías ecuacionales en ACL2

Dado un sistema de ecuaciones E (axiomas), la teoría ecuacional de E es el conjunto de ecuaciones (teoremas) que son consecuencia lógica de E.

Una teoría ecuacional se puede ver como la relación de equivalencia descrita por una reducción: reemplazamiento o reescritura de iguales por iguales, usando los axiomas de la teoría. La teoría ecuacional ha sido expuesta como la equivalencia de una reducción concreta. En ACL2, todo sistema de reescritura noetheriano, cuyos pares críticos confluyen, describe una teoría ecuacional decidible.

Funciones y macros base en ACL2

La gran parte de las funciones base de ACL2 provienen del software Common Lisp. Existen muchas de ellas dedicadas a aritméticas, conversión, reconocedor de números/objetos, etc.

Algunas funciones ejemplo son las siguientes:

(< x y)         Menor estricto
(<= x y)        Menor o igual
(> x y)         Mayor
(>= x y)        Mayor o igual
(+ x y ...)     Suma
(* x y ...)     Multiplicación
(- x y)         Resta
(- x)           Opuesto
(/ x y)         División
(nfix x)        Conversión a número natural
(consp x)       Reconocedor de pares punteados
(atom x)        Reconocedor de objetos atómicos
(true-listp l)  Reconocedor de listas

Referencias

↑ Matt Kaufmann, Panagiotis Manolios, y J Strother Moore (junio de 2000). Computer-Aided Reasoning: An Approach. Kluwer Academic Publishers. ISBN 0-7923-7744-3.
↑ Matt Kaufmann, Panagiotis Manolios, y J Strother Moore, ed. (junio de 2000). Computer-Aided Reasoning: ACL2 Case Studies. Kluwer Academic Publishers. ISBN 0-7923-7849-0.
↑ «ACM Software System Award». ACM. Consultado el 28 de marzo de 2006.

Enlaces externos

Datos: Q4650692

[Kaufmann-1] Matt Kaufmann, Panagiotis Manolios, y J Strother Moore (junio de 2000). Computer-Aided Reasoning: An Approach. Kluwer Academic Publishers. ISBN 0-7923-7744-3.

[Kaufmann2-2] Matt Kaufmann, Panagiotis Manolios, y J Strother Moore, ed. (junio de 2000). Computer-Aided Reasoning: ACL2 Case Studies. Kluwer Academic Publishers. ISBN 0-7923-7849-0.

[BoyerMoore-3] «ACM Software System Award». ACM. Consultado el 28 de marzo de 2006.

[1]

[2]

[3]