Semántica formal de OCaml en Coq

14

La semántica de un gran subconjunto de OCaml, llamada OCamllight , fue formalizada en HOL por Owens hace varios años. Más recientemente, Kreitz, Hayden y Hickey implementaron una semántica teórica tipo de un subconjunto más pequeño de OCaml en Nuprl .

¿Hay algún desarrollo similar en Coq?

coq program-verification ocaml Andrea Asperti
fuente
Quizás te interese CakeML: cakeml.org . Sin embargo, no es OCaml específicamente.
jmite

Respuestas:

12

¿Has visto la tesis doctoral de Arthur Charguéraud, Fórmulas características para la verificación mecanizada de programas ?

En lugar de construir el sistema de tipos y la semántica de pequeños pasos como relaciones inductivas, ofrece una técnica para convertir los programas de Caml en fórmulas características. Esto es básicamente una generalización de la semántica de transformador de predicados para admitir un subconjunto muy grande de Ocaml, en particular, incluyendo lanzamientos inseguros como Obj.magic. Para citar de su tesis:

Me he centrado en un subconjunto del lenguaje de programación OCaml, que es un lenguaje de programación secuencial, llamado por valor y de alto nivel. La implementación actual de CFML es compatible con el cálculo del núcleo λ, que incluye funciones de orden superior, recursión, recursión mutua y recursividad polimórfica. Admite tuplas, constructores de datos, coincidencia de patrones, celdas de referencia, registros y matrices. Proporciono una biblioteca Caml adicional que agrega soporte para punteros nulos y actualizaciones fuertes.

Es un enfoque muy atractivo si desea probar que un programa de Caml en particular es correcto (menos aún si está interesado en su metateoría).

Neel Krishnaswami
fuente
Entonces, si entiendo bien, la especificación de la semántica de Ocaml está integrada en el sistema. ¿Es posible interpretar la fórmula característica de (alguna función clave del) sistema como tal especificación? Además, supongo que el sistema está escrito en OCaml. ¿Es posible especificar y probar su corrección en el propio sistema?
Andrea Asperti
Para un programa OCaml dado, su fórmula característica puede pensarse en una semántica denotacional, una especificación "menos general" que puede usarse para probar cualquier propiedad deseable del programa. Si habla de la "corrección" de CFML, la pregunta es: ¿con respecto a qué semántica formal alternativa?
gasche
Es extraño tener un programa que supuestamente certifique el software y cuyo comportamiento no pueda especificarse :)
Andrea Asperti
@AndreaAsperti ¿Qué quieres decir con "incrustado en el sistema"? La idea detrás de las fórmulas características (CF) es bastante sencilla: mapear programas a fórmulas lógicas (típicamente precondición y poscondición), tales fórmulas describen con precisión la semántica de los programas. En otras palabras, dos programas satisfacen los mismos CF si son contextualmente indistinguibles. El mapa del programa a los CF se realiza por inducción de la estructura del programa, y ​​puede apuntar a cualquier lógica suficientemente expresiva. A. La lógica de Coq del objetivo de Charguéraud, pero esa es una elección contingente.
Martin Berger
1
@MartinBerger: el artículo de Guéneau et al solo prueba la solidez porque los pre / posts derivados no caracterizan los programas de los que derivan. Sus CF se derivan de la semántica sin tipo de CakeML, pero el lenguaje escrito tiene una equivalencia observacional diferente. (Para la verificación práctica, esto no es terriblemente importante, y es más fácil.)
Neel Krishnaswami
8

Usted podría estar interesado en la implementación certificada de ML de Jacques Garrigue de ML con polimorfismo estructural y tipos recursivos , que establece la solidez de la semántica estática y dinámica y las propiedades de inferencia de tipos para un lenguaje ML con polimorfismo estructural (recursivo y), formalizando así uno de los Esquinas más avanzadas de OCaml (variantes polimórficas y tipos de objetos).

Dicho esto, este trabajo está más dirigido a verificar la solidez de las partes más avanzadas del sistema de tipos que a cubrir el conjunto de características de los programas OCaml existentes. Creo que en términos de tratar de probar la corrección de un programa OCaml existente, CFML sería una mejor opción.

gasche
fuente