Estoy interesado en compiladores verificados formalizados en la teoría de tipo Martin-Löf, es decir, Coq / Agda. Por el momento he escrito un pequeño ejemplo de juguete. Con eso puedo demostrar que mis optimizaciones son correctas. Por ejemplo, las adiciones con cero pueden eliminarse, es decir, expresiones como "x + 0".
¿Existen optimizaciones que son difíciles de realizar con un compilador normal, que servirían como un buen ejemplo? ¿Es posible probar ciertas propiedades de un programa que permiten optimizaciones que no son posibles de realizar con un compilador normal? (es decir, sin la inferencia que es posible con un probador de teoremas)
Me interesarían ideas o ejemplos y también referencias sobre el tema.
Una pregunta relacionada: pruebas de corrección del compilador
editar: Como Tsuyoshi lo puso muy bien en los comentarios: estoy buscando técnicas de optimización que son difíciles de implementar si un compilador está escrito en (digamos) C pero más fácil de implementar si un compilador está escrito en (digamos) Coq. A medida que Agda compila en C (a través de Haskell), es posible hacer todo lo posible en Agda también en C. Probablemente el único beneficio de los probadores de teoremas como Coq / Agda es que el compilador y las optimizaciones pueden verificarse.
edit2: Según lo sugerido por Vijay DI, escriba lo que he leído hasta ahora. Me centré principalmente en Xavier Leroy y el proyecto CompCert en INRIA (creo que hay un documento de 80 páginas que es una buena lectura). Un segundo interés estaba en el trabajo de Anton Setzer en programas interactivos. Pensé que tal vez su trabajo podría usarse para probar propiedades sobre los programas IO y la bisimulación de los programas IO. Gracias por mencionar a Sewell. Escuché su charla "Cuentos de la jungla" en ICFP y leí quizás 2-3 de sus documentos. Pero no he visto específicamente su trabajo y el de sus coautores.
Todavía no descubrí por dónde empezar ni busqué documentos sobre la optimización de compiladores; por ejemplo, qué optimizaciones sería interesante observar en la configuración de un compilador verificado.
Respuestas:
Este artículo de Yves Bertot, Benjamin Gr´egoire y Xavier Leroy crea un compilador optimizador para un lenguaje tipo C basado exclusivamente en la especificación Coq. algunos de esta tecnología es aparentemente utilizados en el compilador de C CompCert .
Un enfoque estructurado para probar las optimizaciones del compilador basadas en el análisis del flujo de datos
considera la corrección de dos optimizaciones, propagación constante (CP) y eliminación de subexpresión común (CSE), sección 4. estas optimizaciones son más avanzadas que las que están asociadas con los compiladores no basados en Coq para el mismo lenguaje. ver, por ejemplo, este gráfico de referencia en comparación con gcc. (¡el compilador basado en Coq es presumiblemente más lento de compilar aunque esto rara vez se menciona!)
sin embargo, al final del documento, notan que hay algunas optimizaciones de compiladores en compiladores reales que no se pueden modelar en su marco.
La optimización mejorada no es el único elemento de consideración aquí, otro aspecto es que la lógica de optimización del compilador puede estar sujeta a defectos sutiles, especialmente debido a su naturaleza compleja. Con los años, se ha descubierto que gcc tiene errores en sus numerosas rutinas de lógica de optimización. por ejemplo, error de gcc?
fuente
Es equivalente a extender el typechecker para proporcionar algunas propiedades de un programa al optimizador. Creo que Tsuyoshi Ito tiene razón y puede que estés un poco equivocado sobre Coq. Es una gran herramienta para proporcionar un compilador sin errores, pero en el caso que describa, no proporciona más potencia a los análisis estáticos.
Lo único que puedo pensar en fortalecer los análisis estáticos con Coq es equipar su lenguaje con afirmaciones que contengan algunas pruebas escritas por el usuario. - Si el compilador mismo se tradujera a un lenguaje que incluye una pluma para la verificación dinámica de tipos, y si las pruebas escritas por el usuario fueran convertibles a funciones, entonces sería posible aplicar esas funciones como propiedades requeridas previamente para algunos subtipos u optimizaciones. - De hecho, esto proporcionaría más potencia al compilador.
Sin embargo, hasta donde puedo ver, sería bastante útil para fortalecer el subtipo. - Es difícil hacer que un programador sepa qué propiedad en qué lugar sería útil para el optimizador.
fuente