Las funciones pueden ser probadas Haskell /-comprueba modelo / verificado con propiedades de corrección?

StackOverflow https://stackoverflow.com/questions/4077970

Pregunta

Continuando desde las ideas en: ¿Hay en el mundo real demostrable idiomas?

No sé ustedes, pero yo soy harto de escribir código que no puede garantizar.

Después de pedir a la pregunta anterior y obtener una respuesta fenomenal (Gracias todos!) He decidido reducir mi búsqueda de una demostrable, pragmático, acercamiento a Haskell . Elegí Haskell porque es realmente útil (hay muchos href="http://www.turbinado.org/" rel="noreferrer"> marcos escrito para ella, esto parece un buen punto de referencia) Y Creo que es lo suficientemente estricto, funcionalmente , que podría ser demostrable, o al menos permitir la prueba de invariantes.

Esto es lo que quiero (y han sido incapaces de encontrar)

Quiero un marco que puede mirar a una función Haskell, añadir, escrito en psudocode: 

add(a, b):
    return a + b

- y comprobar si ciertos invarients tienen sobre todos los estados de ejecución. Yo prefiero por alguna prueba formal, sin embargo, me conformaría con algo así como un modelo ortográfico.
En este ejemplo, el invarient sería que los valores dados a y b , el valor de retorno es siempre la suma a + b .

Este es un ejemplo sencillo, pero no creo que es una imposibilidad para un marco como éste de existir. Ciertamente habría un límite superior de la complejidad de una función que podría ser probado (10 entradas cadena a una función sin duda llevar mucho tiempo!) Pero esto alentaría diseño más cuidadoso de las funciones, y no es diferente que cualquier otro formales métodos. Imagine utilizar Z o B, cuando se definen las variables / conjuntos, se hace absolutamente seguro de que usted da a las variables de los rangos más pequeños posibles. Si su INT nunca va a estar por encima de 100, asegúrese de que arranque como tal! Técnicas como estas, y la descomposición adecuada problema deberían - creo -. Permitir la comprobación satisfactoria de un lenguaje funcional puro como Haskell

No soy - todavía - con mucha experiencia con los métodos formales o Haskell. Déjeme saber si mi idea es un sonido, o tal vez usted piensa que Haskell no es adecuado? Si usted sugiere un idioma diferente, por favor asegúrese de que pasa el "has-a-web-marco" prueba y hacer leer el original pregunta : -)

¿Fue útil?

Solución

Bueno, algunas cosas para empezar, ya que usted está tomando la ruta Haskell:

  • ¿Está familiarizado con el Curry-Howard correspondencia ? Hay sistemas utilizados para las pruebas de la máquina-facturado en base a este que son, en muchos sentidos, lenguajes de programación, simplemente funcionales con sistemas de tipo muy potentes.

  • ¿Está familiarizado con las áreas de la matemática abstracta que proporcionan conceptos útiles para el análisis de código Haskell? Varios sabores de álgebra y algunos fragmentos de la teoría de categorías suben mucho.

  • Tenga en cuenta que Haskell, al igual que todos los idiomas Turing completo, siempre tiene la posibilidad de nontermination. En general, es mucho más difícil de probar que algo va a siempre ser verdad de lo que es para probar que sea algo va a ser verdad o dependerá de un valor sin terminación.

Si usted está seriamente ir a prueba , no meramente testing , estos son el tipo de cosas a tener en cuenta. La regla básica es la siguiente: hacer que los estados no válidos causa errores de compilación. Prevenir la inválido datos de ser codificado en el primer lugar, y luego dejar que el tipo de corrector hacer la parte tediosa para usted.

Si quiere ir aún más lejos, si la memoria no me falla la prueba de asistente Coq tiene una "extracto de Haskell" característica que le permitirá probar las propiedades arbitrarias sobre las funciones críticas, a continuación, gire las pruebas en código Haskell.

Para hacer el tipo de fantasía cosas sistema directamente en Haskell, Oleg Kiselyov es la Gran Maestro. Se pueden encontrar ejemplos en su sitio de truquitos como de mayor rango tipos polimórficos a pruebas estáticas de codificación límites de la matriz de comprobar .

Para la materia más ligero, que puede hacer cosas como utilizando un tipo de certificado -level para marcar una hoja de datos como habiendo sido verificado su corrección. Todavía estás en tu propio para la propia comprobación de exactitud, pero sí puede codificar al menos confía en el conocimiento de que algunos datos, de hecho, ha comprobado.

Otro paso que puede tomar, la construcción fuera de la verificación ligero y trucos sistema de tipo de fantasía, es utilizar el hecho de que Haskell funciona bien como una lengua de acogida para incrustar -dominio específico idiomas ; primero construir un sublenguaje cuidadosamente restringida (idealmente, uno que no es Turing completo) sobre el que permite demostrar más fácilmente propiedades útiles, a continuación, utilizar los programas en ese DSL para proporcionar piezas clave de la funcionalidad básica de su programa general. Por ejemplo, se puede demostrar que una función de dos argumentos es asociativa con el fin de justificar la reducción parallelized de una colección de artículos que utilizan esa función (ya que el orden de aplicación de función no importa, sólo el orden de los argumentos).

Ah, una última cosa. Algunos consejos para evitar las trampas que Haskell contiene, que puede sabotear código que de otro modo sería segura por la construcción: Sus enemigos jurados aquí son recursión en general , IO mónada y funciones parciales :

  • La última es relativamente fácil de evitar: No escribir ellos, y no los utilizan. Asegúrese de que cada conjunto de patrón coincide con asas todos los casos posibles, y nunca utilizar error o undefined. La única parte difícil es evitar las funciones de la biblioteca estándar que pueden causar errores. Algunos son obviamente insegura, como fromJust :: Maybe a -> a o head :: [a] -> a pero otros pueden ser más sutiles. Si usted se encuentra escribiendo una función que realmente, realmente no se puede hacernada con algunos valores de entrada, entonces usted está permitiendo que los estados no válidos a ser codificados por el tipo de entrada y necesidad de arreglar eso, en primer lugar.

  • El segundo es fácil de evitar en un nivel superficial por la dispersión de la materia a través de funciones puras surtidos que se utilizan a continuación, a partir de una expresión IO. Mejor es que, en lo posible, mover todo el programa a cabo en código puro para que pueda ser evaluada de forma independiente con todo, pero la E / S real. Esto sobre todo se vuelve complicado sólo cuando sea necesario recursividad que está impulsado por una entrada externa, lo que me lleva al último punto:

  • Palabras a las prudentes: recursión fundados Bien y corecursion productiva . Asegúrese siempre de que las funciones recursivas van ya sea desde un punto de partida a un caso base conocido, o están generando una serie de elementos en la demanda. En el código puro, la forma más fácil de hacer esto es por cualquiera de colapsar de forma recursiva una estructura de datos finita (por ejemplo, en lugar de una función que se hace llamar directamente, mientras que incrementar un contador hasta algún máximo, crear una lista de la celebración de la gama de valores de contador y doblar ) o la generación de una estructura de datos recursiva perezoso (por ejemplo, una lista de aproximaciones progresivas a un cierto valor), mientras que cuidadosamente Nunca mezclar los dos directamente (por ejemplo, no sólo "encontrar el primer elemento en el flujo de cumplir alguna condición"; tal vez no existir. en su lugar, tomar valores de la corriente hasta una cierta profundidad máxima, a continuación, buscar en la lista finita, que lleva el caso que no se encuentra-apropiado).

  • La combinación de los dos últimos puntos, para las partes donde realmente es necesario IO con recursividad en general, tratar de construir el programa como componentes adicionales, a continuación se condensan todos los bits incómodas en una sola función "controlador". Por ejemplo, se podría escribir un bucle de eventos GUI con una función puro como mainLoop :: UIState -> Events -> UIState, una prueba de salida como quitMessage :: Events -> Bool, una función para obtener la espera de acontecimientos getEvents :: IO Events, y un updateUI :: UIState -> IO () función de actualización, a continuación, ejecutar realmente la cosa con una función generalizada como runLoopIO :: (b -> a -> b) -> b -> IO a -> (b -> IO ()) -> IO (). Esto evita que las partes complicadas verdaderamente pura, lo que le permite ejecutar todo el programa con un script de evento y comprobar el estado de la interfaz de usuario resultante, al tiempo que aísla las partes incómodas recursiva de E / S en una sola función, abstracta que es fácil de comprender y con frecuencia será inevitablemente correcta parametricity .

Otros consejos

Probablemente lo más parecido a lo que estás pidiendo es Haskabelle , una herramienta que viene de su auxiliar prueba Isabelle que puede traducir archivos Haskell en teorías Isabelle y le permite probar cosas acerca de ellos. Por lo que yo entiendo esta herramienta se desarrolla dentro del HOL - ML - Haskell proyecto y la página de documentación contiene alguna información acerca de la teoría detrás.

No estoy terriblemente familiarizado con este proyecto y no sé mucho acerca de lo que se ha hecho con él. Pero sé Brian Huffman ha estado jugando un poco con estas cosas, echa un vistazo a sus papeles y conversaciones, deben contener material relevante.

No estoy seguro de si lo que se pide es en realidad lo que te hará feliz. : -)

Modelo de comprobación de un lenguaje de propósito general es neigh imposible ya que los modelos deben ser específicos de dominio para ser práctico. Debido a de Gödel incompletitud teorema, simplemente es ningún método para encontrar automáticamente pruebas en una lógica suficientemente expresivo.

Esto significa que usted tiene que escritura pruebas por tu , lo que plantea la cuestión de si el esfuerzo vale la pena el tiempo invertido. Por supuesto, el esfuerzo crea algo muy valioso, a saber, la seguridad de que su programa es correcto. La cuestión no es si se trata de una herramienta imprescindible, pero si el tiempo es un precio demasiado alto. Lo que pasa es que, si bien las pruebas que pueda tener un "intuitiva" entendiendo que su programa es correcta , a menudo es muy difícil de formalizar este entendimiento como una prueba. El problema con la comprensión intuitiva es que es altamente susceptible a errores accidentales (errores tipográficos y otros errores estúpidos). Este es el dilema básico de escribir programas correctos.

Por lo tanto, la investigación sobre la corrección del programa se trata de hacer que sea más fácil para formalizar las pruebas y comprobar su corrección automática. La programación es una parte integral de la "facilidad de formalización"; es muy importante para los programas de escritura en un estilo que es fácil de razonar acerca. Actualmente, tenemos el siguiente espectro:

  • lenguaje imperativo como C, C ++, Fortran, Python: Muy difícil de formalizar cualquier cosa aquí. Las pruebas unitarias y el razonamiento general, son la única forma de obtener al menos alguna seguridad. Capturas tipos estáticos sólo errores triviales (que no mucho mejor que la captura de ellos!).

  • lenguajes puramente funcionales como Haskell, ML: sistema de tipo expresivo ayuda a los errores y los errores de captura no triviales. Demostrando corrección a mano es práctico para los fragmentos de hasta algún lugar alrededor de 200 líneas, diría yo. (Hice una prueba para mi paquete operativa, por ejemplo.) prueba QUICKCHECK es un sustituto barato de pruebas formales.

  • idiomas Dependientemente mecanografiados y asistentes a prueba como Agda, epigrama, Coq: Probar programas enteros correcta es posible gracias a la ayuda automatizada con la formalización prueba y el descubrimiento. Sin embargo, la carga sigue siendo alta.

En mi opinión, el punto dulce corriente para escribir programas correctos es programación puramente funcional . Si vidas dependen de la exactitud de su programa, es mejor ir a un nivel más alto y utilizar un asistente prueba.

Parece que usted quiere ESC / Haskell: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/index.htm

Ah, y Agda ahora tiene un marco Web (prueba de concepto, por lo menos): http://www.reddit.com/r/haskell/comments/d8dck/lemmachine_a_web_framework_in_agda/

¿Ha tenido un vistazo a QuickCheck? Se puede ofrecer algunas de las cosas que necesita.

http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck

Su ejemplo aparentemente simple, add (a, b), en realidad es difícil de verificar -. Coma flotante, desbordamiento, desbordamiento, interrupciones, es el compilador verifica, es el hardware verificada, etc.

hábito es un dialecto simplificado de Haskell que permite probar las propiedades del programa.

Hume es una lengua con 5 niveles, cada uno más limitedand tanto más fácil de verificar: 

Full Hume
  Full recursion
PR−Hume
  Primitive Recursive functions
Template−Hume
  Predefined higher−order functions
  Inductive data structures
  Inductive  Non−recursive first−order functions
FSM−Hume
  Non−recursive data structures
HW−Hume
  No functions
  Non−recursive data structures

Por supuesto, el método más popular de hoy en día para probar las propiedades del programa es la unidad de pruebas, que proporciona teoremas fuertes, pero estos teoremas son excesivamente específica. "Tipos consideran perjudiciales", Pierce, deslice 66

Tener un vistazo a Zeno . Citando la página wiki:

  

Zeno es un sistema de prueba automatizado para propiedades del programa Haskell; desarrollado en el Imperial College de Londres por William Sonnex, Sophia Drossopoulou y Susan Eisenbach. Su objetivo es resolver el problema general de igualdad entre dos términos Haskell, para cualquier valor de entrada.

     

Muchas herramientas de verificación de programas disponibles en la actualidad son de la variedad verificación de modelos; capaz de atravesar una muy grande pero finita espacio de búsqueda muy rápidamente. Estos son muy adecuadas para los problemas con una descripción grande, pero no hay tipos de datos recursivas. Zeno, por otro lado está diseñado para probar inductivamente propiedades durante un espacio de búsqueda infinita, pero sólo aquellos con una especificación pequeño y simple.

Es ciertamente posible probar algunos propiedades de los programas Haskell formalmente. He tenido que hacerlo en mi FP examen: dado dos expresiones, demuestran que denotan la misma función. No es posible hacer esto en general, ya que Haskell es Turing completo, por lo que cualquier cámara de fermentación mecánica sería tampoco tiene por qué ser un ayudante de la prueba (semi-automática con guía de usuario) o un comprobador de modelos.

Ha habido intentos en esta dirección, véase, por ejemplo P-lógica: verificación de la propiedad para Haskell programas o < a href = "http://mizar.org/trybulec65/14.pdf" rel = "nofollow"> la demostración de la corrección de los programas funcionales utilizando Mizar . Ambos son trabajos académicos que describen los métodos más implementaciones.

La herramienta aprove es (al menos) capaz de demostrar la terminación de los programas de Haskell, que es parte de la prueba de corrección. Más información se puede encontrar en este papel ( versión más corta ).

Además de eso, usted puede estar interesado en tipos dependientes . En este caso, el sistema de tipos se extiende y se utiliza para hacer programas equivocados imposible.

Puede utilizar la herramienta hs-to-coq para convertir Haskell su mayoría automática en Coq, y luego utilizar toda la potencia de la prueba Coq asistente para verificar su código de Haskell. Ver los documentos https://arxiv.org/abs/1803.06960 y https://arxiv.org/abs/1711.09286 de algo más de información.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top