Herramienta de prototipos de semántica de lenguaje de programación

11

¿Existe alguna herramienta para la creación de prototipos de una semántica de lenguaje de programación y un sistema de tipos y que también permita algún tipo de verificación de modelo de propiedades estándar, como la solidez de tipo?

Pregunto esto, porque estoy leyendo un libro sobre Alloy y proporciona la funcionalidad exacta que quiero, pero para los modelos expresados ​​con lógica relacional.

Soy consciente de Ott , pero no tiene este tipo de capacidad de "comprobación de modelo", ya que se centra en generar código para sistemas de asistente de prueba.

Cualquier referencia sobre la existencia de dicha herramienta sería buena.

Rodrigo Ribeiro
fuente
1
Ott es el primer paso, luego verifica el modelo en su asistente de prueba favorito.
Gilles 'SO- deja de ser malvado'
@Gilles: Ok, pero un punto de una herramienta de verificación de modelos es que genera un conjunto completo de elementos de un tamaño determinado para verificar si la propiedad es realmente válida para ellos. De esta manera, necesitaré codificar esta parte de generación para cada idioma definido. ¿Sabía si hay alguna forma de automatizar este paso de generación?
Rodrigo Ribeiro el
Técnicamente, puede hacer esto en un asistente de prueba (al menos en uno como Coq) pero probablemente será muy lento. Los asistentes de prueba están orientados a pruebas asistidas por humanos en lugar de intentar automáticamente millones de formas de resolver el problema. Si desea reutilizar Ott, puede agregar un back-end para su verificador de modelos favorito.
Gilles 'SO- deja de ser malvado'

Respuestas:

8

Aunque existen marcos creados específicamente con el propósito de crear prototipos de lenguajes de programación (incluida su semántica, sistemas de tipos, evaluación, así como verificar propiedades sobre ellos), la mejor opción depende de su caso particular y necesidades específicas.

Dicho esto, hay varias alternativas (quizás no tan distintas) que podría tomar (que incluyen las que ya ha mencionado):

  • utilizando un lenguaje / marco específico diseñado para crear y crear prototipos de nuevos lenguajes: como ejemplo, Redex [1], un lenguaje específico de dominio integrado en Racket para especificar y verificar la semántica (operativa) de lenguajes de programación, que, dada la definición de un lenguaje, proporciona un manejo sencillo de tareas como la composición tipográfica (en Latex), la inspección de rastros de reducción, pruebas unitarias y pruebas aleatorias (por ejemplo, para verificar la escritura)
  • utilizando lenguajes de modelado generales que ofrecen la definición y realización de ciertos análisis fácilmente, siempre que puedan capturar el lenguaje específico disponible en la medida necesaria; Alloy [2] es un ejemplo de este enfoque: aunque es bastante general y flexible, los lenguajes pueden modelarse como relaciones entre estados, mientras que el soporte para la verificación de modelos (por ejemplo, la evaluación dentro de dicho lenguaje) es gratuito después de que la semántica se expresa con un modelo de relación (por ejemplo, algunas ideas para modelar la semántica de un lenguaje se pueden encontrar en [3])
  • incrustando el lenguaje para verificar sus propiedades usando un probador de teoremas; un ejemplo definiría el lenguaje así como su semántica incrustándolo en un sistema de prueba como Coq [4] (más detalles sobre este enfoque, así como una discusión y demostración de la diferencia entre la incrustación profunda y superficial en Coq se da en [ 5])
  • usando Ott (como ya se mencionó, con un espíritu similar al de Redex, pero brindando un nuevo lenguaje de definición en lugar de ser incrustado); Ott le permite definir el lenguaje de programación en una notación conveniente y producir la composición tipográfica y las definiciones en un sistema de prueba (generalmente con incrustación profunda), donde la mayor parte de la verificación (es decir, la prueba) debe realizarse manualmente
  • desarrollando el lenguaje y su semántica, así como las comprobaciones apropiadas (por ejemplo, como pruebas) "desde cero" en un lenguaje de programación de propósito general y la traducción a otros sistemas si es necesario, para fines de comprobación (algunos lenguajes, como Leon [6], incluir verificadores integrados, que permiten probar automáticamente ciertas propiedades y hacen que este enfoque sea similar a la inclusión en un sistema de prueba)

Tenga en cuenta que existe una compensación entre lo fácil que es usar el marco / herramienta (por ejemplo, tan fácil como presentar la definición en papel o en Latex) y cuán poderosos son los mecanismos para verificar las propiedades del lenguaje (por ejemplo, incrustar el el lenguaje en un probador de teoremas puede permitir verificar propiedades muy elaboradas).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt y Robert Bruce Findler. Ejecute su investigación: sobre la efectividad de la mecanización ligera. POPL, 2012.

[2] Daniel Jackson. Aleación: una notación de modelado de objetos livianos. TOSEM, 2002.

[3] Greg Dennis, Felix Chang, Daniel Jackson. Verificación modular de código con SAT. ISSTA, 2006

[4] Sistema de gestión de pruebas formales Coq

[5] Razonamiento formal sobre los programas. Adam Chlipala, 2016

[6] Sistema automatizado Leon para verificar, reparar y sintetizar programas Scala funcionales

ivcha
fuente