tuplas sobre simbolos opciones multiplos multiplicar hacer funciones ejemplos como basico testing haskell functional-programming formal-methods formal-verification

testing - sobre - multiplos en haskell



¿Pueden las funciones de Haskell ser probadas/verificadas por modelo/verificadas con propiedades de corrección? (11)

Continuando con las ideas en: ¿Hay algún lenguaje del mundo real demostrable?

No sé ustedes, pero estoy harto de escribir código que no puedo garantizar.

Después de formular la pregunta anterior y obtener una respuesta fenomenal (¡Gracias a todos!), He decidido limitar mi búsqueda de un enfoque comprobable y pragmático para Haskell . Elegí Haskell porque en realidad es útil (hay many frameworks web escritos para él, este parece ser un buen punto de referencia) Y creo que es lo suficientemente estricto, functionally , que podría ser comprobable, o al menos permitir la prueba de invariantes.

Esto es lo que quiero (y no he podido encontrar)

Quiero un marco que pueda ver una función de Haskell, agregar, escrito en psudocódigo:

add(a, b): return a + b

- y compruebe si ciertos invariantes mantienen cada estado de ejecución. Preferiría una prueba formal, sin embargo, me conformaría con algo así como un modelo de corrector.
En este ejemplo, el invariente sería aquel dado por los valores a y b , el valor de retorno siempre es la suma a + b .

Este es un ejemplo simple, pero no creo que sea imposible que exista un marco como este. Ciertamente habría un límite superior en la complejidad de una función que podría ser probada (¡10 entradas de cadena para una función tomaría ciertamente un largo tiempo!) Pero esto alentaría un diseño de funciones más cuidadoso, y no es diferente a usar otras formas formales. métodos. Imagine usar Z o B, cuando defina variables / conjuntos, asegúrese de dar a las variables los rangos más pequeños posibles. Si su INT nunca va a estar por encima de 100, ¡asegúrese de inicializarlo como tal! Técnicas como estas, y la descomposición adecuada del problema deberían, creo, permitir una verificación satisfactoria de un lenguaje puramente funcional como Haskell.

Todavía no tengo mucha experiencia con los métodos formales o con Haskell. Avíseme si mi idea es sensata o tal vez piense que haskell no es adecuado. Si sugiere un idioma diferente, asegúrese de que pase la prueba "has-a-web-framework" y lea la pregunta original :-)

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

  • ¿Estás familiarizado con la correspondencia de Curry-Howard ? Hay sistemas que se usan para verificaciones de máquina basadas en esto que son, en muchos sentidos, simplemente lenguajes de programación funcionales con sistemas de tipo muy poderoso.

  • ¿Está familiarizado con las áreas de las matemáticas abstractas que proporcionan conceptos útiles para analizar el código Haskell? Varios sabores de álgebra y algunos bits de la teoría de categorías surgen mucho.

  • Tenga en cuenta que Haskell, como todos los lenguajes completos de Turing, siempre tiene la posibilidad de la no determinación. En general, es mucho más difícil demostrar que algo siempre será cierto que demostrar que algo será cierto o dependerá de un valor no determinante.

Si realmente está buscando pruebas , no meramente pruebas , estas son el tipo de cosas a tener en cuenta. La regla básica es esta: Hacer que los estados no válidos provoquen errores en el compilador. Evite que los datos no válidos se codifiquen en primer lugar, luego permita que el verificador de tipos haga la parte tediosa por usted.

Si quiere ir más lejos, si la memoria me sirve, el asistente de pruebas Coq tiene una función de "extraer a Haskell" que le permitirá probar propiedades arbitrarias sobre funciones críticas, luego convierta las pruebas en código Haskell.

Para hacer cosas de sistema de tipo sofisticado directamente en Haskell, Oleg Kiselyov es el Gran Maestro . Puede encontrar ejemplos en su sitio de trucos aseados como tipos polimórficos de alto rango para codificar pruebas estáticas de comprobación de límites de matriz .

Para cosas más livianas, puede hacer cosas como usar un certificado de nivel de tipo para marcar que una pieza de datos ha sido verificada para verificar que sea correcta. Todavía está solo para la comprobación de la corrección, pero otro código puede al menos confiar en saber que, de hecho, se han verificado algunos datos.

Otro paso que puede seguir, aprovechando la verificación liviana y los trucos de sistema de tipo sofisticado, es utilizar el hecho de que Haskell funciona bien como lenguaje de host para incrustar lenguajes específicos de dominio ; primero construya un sublenguaje cuidadosamente restringido (idealmente, uno que no sea Turing-completo) sobre el cual pueda probar propiedades útiles más fácilmente, luego use programas en esa DSL para proporcionar las piezas clave de la funcionalidad central en su programa general. Por ejemplo, podría probar que una función de dos argumentos es asociativa para justificar la reducción paralelizada de una colección de elementos que utilizan esa función (ya que el orden de la aplicación de la función no importa, solo el orden de los argumentos).

Oh, una última cosa. Algunos consejos para evitar las trampas que contiene Haskell, que pueden sabotear el código que de otra manera sería seguro para la construcción: Sus enemigos jurados aquí son la recursión general , la mónada IO y las funciones parciales :

  • Lo último es relativamente fácil de evitar: no los escriba, y no los use. Asegúrese de que cada conjunto de coincidencias de patrones maneje todos los casos posibles, y nunca use error o undefined . La única parte difícil es evitar las funciones de biblioteca estándar que pueden causar errores. Algunos son obviamente inseguros, como de fromJust :: Maybe a -> a o head :: [a] -> a pero otros pueden ser más sutiles. Si te encuentras escribiendo una función que realmente, realmente no puede hacer nada con algunos valores de entrada, entonces estás permitiendo que los estados no válidos sean codificados por el tipo de entrada y necesites reparar eso, primero.

  • El segundo es fácil de evitar en un nivel superficial al dispersar cosas a través de funciones puras surtidas que luego se utilizan desde una expresión IO . Lo mejor es, en la medida de lo posible, mover todo el programa en código puro para que pueda evaluarse independientemente con todo menos con la E / S real. Esto en su mayoría se vuelve complicado solo cuando se necesita recursividad impulsada por entrada externa, lo que me lleva al último elemento:

  • Palabras al sabio: recursión bien fundada y corecursion productiva . Asegúrese siempre de que las funciones recursivas vayan desde un punto inicial a un caso base conocido o generen una serie de elementos a pedido. En código puro, la forma más fácil de hacerlo es mediante el colapso recursivo de una estructura de datos finita (por ejemplo, en lugar de llamar directamente a una función al aumentar un contador hasta un máximo, crear una lista que contenga el rango de valores del contador y doblarla) ) o recursivamente generando una estructura de datos perezosa (por ejemplo, una lista de aproximaciones progresivas a algún valor), mientras que nunca mezcla los dos directamente (por ejemplo, no solo "encuentre el primer elemento en la secuencia que cumpla alguna condición"; podría no existe. En su lugar, tome valores de la transmisión hasta una profundidad máxima, luego busque en la lista finita, maneje el caso no encontrado de forma apropiada).

  • Combinando los dos últimos elementos, para las partes donde realmente necesita IO con recursión general, intente construir el programa como componentes incrementales, luego condense todos los bits incómodos en una sola función de "controlador". Por ejemplo, podría escribir un bucle de evento GUI con una función pura como mainLoop :: UIState -> Events -> UIState , una prueba de salida como quitMessage :: Events -> Bool , una función para obtener eventos pendientes getEvents :: IO Events , y una función de actualización updateUI :: UIState -> IO () , luego ejecuta realmente la cosa con una función generalizada como runLoopIO :: (b -> a -> b) -> b -> IO a -> (b -> IO ()) -> IO () . Esto mantiene las partes complicadas verdaderamente puras, permitiéndole ejecutar todo el programa con un script de evento y verificar el estado resultante de la IU, al tiempo que aisla las incómodas partes recursivas de E / S en una sola función abstracta que es fácil de comprender y que a menudo será inevitablemente correcta por parametricity .

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

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

Muchas herramientas de verificación de programas disponibles en la actualidad son de la variedad de comprobación de modelos; capaz de atravesar un espacio de búsqueda muy grande pero finito muy rápidamente. Estos son adecuados para problemas con una descripción grande, pero no para tipos de datos recursivos. Zeno, por otro lado, está diseñado para probar inductivamente las propiedades en un espacio de búsqueda infinito, pero solo aquellas con una especificación pequeña y simple.

La herramienta AProVE es (al menos) capaz de demostrar la finalización de los programas de Haskell, lo cual es parte de probar la corrección. Se puede encontrar más información en este documento ( versión más corta ).

Aparte de eso, es posible que le interesen los tipos dependientes . Aquí, el sistema de tipo se extiende y se usa para hacer que los programas incorrectos sean imposibles.

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

La verificación de modelos de un lenguaje de propósito general es casi imposible ya que los modelos deben ser específicos del dominio para ser prácticos. Debido al Teorema de Incompletitud de Gödel, simplemente no hay un método para encontrar pruebas automáticamente en una lógica suficientemente expresiva.

Esto significa que tiene que escribir pruebas usted mismo , 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 pregunta no es si esto es imprescindible, sino si el tiempo invertido es demasiado costoso. Lo que pasa con las pruebas es que, si bien puede tener una comprensión "intuitiva" de que su programa es correcto , a menudo es muy difícil formalizar esta comprensión como una prueba. El problema con la comprensión intuitiva es que es muy 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 tiene que ver con facilitar la formalización de las pruebas y verificar su corrección de forma automática. La programación es una parte integral de la "facilidad de formalización"; es muy importante escribir programas en un estilo que sea fácil de razonar. Actualmente, tenemos el siguiente espectro:

  • Lenguaje imperativo como C, C ++, Fortran, Python: Muy difícil formalizar algo aquí. Las pruebas unitarias y el razonamiento general son la única manera de obtener al menos alguna seguridad. El tipado estático detecta solo errores triviales (¡lo cual es mucho mejor que no detectarlos!).

  • Los lenguajes puramente funcionales como Haskell, ML: el sistema de tipo expresivo ayuda a detectar errores y errores no triviales. Probar la corrección a mano es práctico para fragmentos de hasta aproximadamente 200 líneas, diría yo. (Hice una prueba para mi paquete operacional , por ejemplo.) Quickcheck pruebas Quickcheck son un sustituto barato de las pruebas formalizadas.

  • Lenguajes dependientes y asistentes de prueba como Agda, Epigram, Coq: la prueba de programas completos correctos es posible gracias a la ayuda automatizada con formalización y descubrimiento de pruebas. Sin embargo, la carga sigue siendo alta.

En mi opinión, el punto óptimo actual para escribir programas correctos es la programación puramente funcional . Si las vidas dependen de lo correcto de su programa, será mejor que suba un nivel más alto y use un asistente de pruebas.

Probablemente lo más parecido a lo que estás pidiendo es a Haskabelle , una herramienta que viene con la asistente de pruebas Isabelle que puede traducir los archivos de Haskell a las teorías de Isabelle y te permite probar cosas sobre ellos. Por lo que yo entiendo, esta herramienta se desarrolla dentro del proyecto HOL - ML - Haskell y su página de inicio contiene cierta información sobre la teoría detrás.

No estoy muy familiarizado con este proyecto y no sé mucho sobre lo que se ha hecho con él. Pero sé que Brian Huffman ha estado jugando con estas cosas, revisando sus documentos y charlas, deberían contener material relevante.

Sin duda es posible probar algunas propiedades de los programas Haskell formalmente. He tenido que hacerlo en mi examen FP: dadas dos expresiones, pruebo que denotan la misma función. No es posible hacerlo en general ya que Haskell es Turing-completo, por lo que cualquier probador mecánico tendría que ser un asistente de prueba (semiautomático con guía del usuario) o un verificador de modelo.

Ha habido intentos en esta dirección, ver, por ejemplo, P-logic: verificación de propiedad para programas Haskell o Probar la corrección de programas funcionales utilizando Mizar . Ambos son trabajos académicos que describen métodos más que implementaciones.

Su ejemplo aparentemente simple, add (a, b), es realmente difícil de verificar: punto flotante, desbordamiento, subdesbordamiento, interrupciones, se verifica el compilador, se verifica el hardware, etc.

Habit es un dialecto simplificado de Haskell que permite probar las propiedades del programa.

Hume es un lenguaje con 5 niveles, cada uno más limitado y por lo 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 hoy en día para probar las propiedades del programa es la prueba unitaria, que proporciona sólidos teoremas, pero estos teoremas son demasiado específicos. "Tipos considerados dañinos", Pierce, diapositiva 66