Reseña: A certified JavaScript interpreter

Se ha publicado un nuevo trabajo de formalización en Coq titulado A certified JavaScript interpreter.

El autor del trabajo es Martin Bodin (del INRIA de Rennes) en colaboración con Alan Schmitt y Thomas Jensen.

El trabajo es parte del proyecto JSCert cuyo objetivo es la construcción de modelos de JavaScript en Coq y el desarrollo de herramientas de análisis automático basadas en dichos modelos.

El resumen del trabajo es

Although it was initially designed for running small scripts in web pages, JavaScript has become the programming language of the web. It is designed to be very dynamic, for instance by allowing the evaluation of strings as code or by letting programmers to explicitly specify the scope in which a program runs. These aspects allow for great flexibility, but significantly hinder the understanding of the semantics of programs, such as the development of certified analyses.

In practice, it is frequent to insert external code in a web page (such as an advertisement or an interactive map) and make it interact with some scripts carrying some potentially secret information. It would be useful to be able to prove the safety of a web page despite the presence of unknown (thus untrusted) code.

In this internship, we present a formalisation in Coq of JavaScript’s semantics. Our main result is a JavaScript interpreter proven correct with respect to the Coq’s semantics. This work is the first step in the building of certified analysers.

Reseña: Mechanization of an algorithm for deciding KAT terms equivalence

Se ha publicado un nuevo trabajo sobre verificación formal en Coq: Mechanization of an algorithm for deciding KAT terms equivalence.

Sus autores son Nelma Moreira, David Pereira y Simao Melo de Sousa (de la Universidade do Porto, Portugal).

Su resumen es

This work presents a mechanically verified implementation of an algorithm for deciding the (in-)equivalence of Kleene algebra with tests (KAT) terms. This mechanization was carried out in the Coq proof assistant. The algorithm decides KAT terms equivalence through an iterated process of testing the equivalence of their partial derivatives. It is a purely syntactical decision procedure and so, it does not construct the underlying automata. The motivation for this work comes from the possibility of using KAT encoding of propositional Hoare logic for reasoning about the partial correctness of imperative programs.

El código de la formalización en Coq se encuentra aquí.

Centenario del Principia Mathematica

Con motivo del centenarario de la publicación del primer volumen del Principia Mathematica de Alfred North Whitehead y Bertrand Russell se está publicando distintos artículos conmemorativos.

Hace dos semanas, El País publicó el artículo de José Manuel Sánchez Ron El valor del fracaso digno.

En el artículo se que comenta que aunque el Principia Mathematica de Whithead y Russell no conseguió su fin (reducir la metemática a la lógica) en cambio, por lo riguroso de sus análisis lógicos y la ambiciosa meta que perseguía, se convirtió en una referencia obligada de toda la lógica y la filosofía de la matemática posteriores. En el artículo recuerda la que le escribión de Alice Mary Hilton a Russell: “Estoy segura de que Principia Mathematica no será olvidado mientras exista una civilización que conserve los trabajos de las mentes realmente grandes”. El artículo termina reflexionando sobre los fines y los medios

No hay que esforzarse mucho en argumentar que poner los fines por encima de los medios constituye una perversión que puede destruir una sociedad. Tal vez sí que haya que detenerse más en señalar que el éxito en una empresa no es siempre lo único que se recuerda. También recordamos, debemos recordar, a los que se esforzaron en empresas exigentes. Aunque fracasasen. Como Whitehead y Russell en Principia Mathematica.

Hace unos días se ha publicado un nuevo artículo conmemorativo:
100 Years Since Principia Mathematica, escrito Stephen Wolfram (el autor del sistema de cálculo simbólico Mathematica y del sistema de búsqueda Wolfram Alpha).

El artículo comienza con un comentario sobre un objetivo compartido por los Principia Mathematica y Mathematica: la formalización de las matemáticas. Realiza un recorrido histórico sobre la formalización de la matemática hasta la publicación de los Principia Mathematica. Compara los avances realizados desde los Principia Mathematica en el razonamiento y en el cálculo simbólico:

In the hundred years since Principia Mathematica, there has been slow progress in presenting theorems of mathematics in formal ways. But the idea of mathematical computation has taken off spectacularly — and has transformed the use of mathematics, and many areas of its development.

El artículo termina con una visión del futuro

In the future, however, I suspect that there will be another level of automation. Probably it will take much less than a hundred years, but in time it will become commonplace not just to make computations to order, but to make to order the very systems on which those computations are based—in effect in the blink of an eye inventing and developing something like a whole Principia Mathematica to respond to some particular purpose.

Formalizaciones en PVS y el problema de las versiones

En la wiki del Grupo de Lógica Computacional se han publicados las formalizaciones en PVS 4.2 de las siguientes teorías:

La adaptación la ha realizado María J. Hidalgo a partir de la versión de PVS 3.2. El proceso de adaptación ha sido complejo por las diferencias existentes entre ambas versiones de PVS. Los principales problemas que han aparecido son los siguientes:

  • Diferencia en el tratamiento de los juicios entre teorías situadas en distintos directorios y cargadas como extensiones del preludio.
  • Diferencia en las opciones por defecto en estrategias predefinidas.
  • Diferencia en el número de obligaciones de pruebas generadas.

Además, el problema de la compatibilidad entre las distintas versiones de los sistemas de razonamiento dificulta la reutilización de las teoría formalizadas. En concreto, en algunas teorías que hemos desarrollado se han usado teorías desarrolladas por otros como, por ejemplo, la teoría sobre puntos fijos de F. Bartels, A. Dold, F.W. v. Henke, H. Pfeifer y H. Rueß que está desarrollada en la versión 2.4 de PVS, no se ha adaptado a las siguientes versiones y no es adecuada para la versión actual de PVS.

Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Se ha publicado un nuevo artículo de formalización: Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks

Los autores del artículo son Freek Verbeek y Julien Schmaltz de la Universiad de Radboud en Nimega (en neerlandés: Nijmegen), Paises Bajos.

El artículo se publicó ayer (18 de Septiembre de 2010) en el Journal of Automated Reasoning.

Una versión preliminar del artículo puede leerse aquí y el código ACL2 correspondiente puede obtenerse aquí

El artículo es una demostración en ACL2 de una condición necesaria y suficiente para enrutamiento sin estancamiento introducida por William J. Dally y Charles L. Seitz en su artículo Deadlock Free Message Routing in Multiprocessor Interconnection Networks de 1987.
Read More “Proof Pearl: A Formal Proof of Dally and Seitz’ Necessary and Sufficient Condition for Deadlock-Free Routing in Interconnection Networks”