Pruebas de un compilador optimizador generando términos lambda aleatorios

Este artículo considera las pruebas aleatorias de un compilador, utilizando programas generados aleatoriamente como entradas y comparando su comportamiento con y sin optimización. Dado que los programas generados deben compilar, necesitamos tener en cuenta la sintaxis, las reglas de alcance y la verificación de tipos durante nuestra generación aleatoria. Hacerlo, mientras se logra una buena distribución de datos de prueba, resulta sorprendentemente sutil; la principal contribución de este artículo es una solución viable a este problema. Lo utilizamos para generar funciones tipadas sobre listas, que compilamos usando el compilador Glasgow Haskell, un compilador de Haskell de calidad de producción madura. Después de alrededor de 20,000 pruebas, provocamos una falla en el optimizador y lo simplificamos automáticamente a un programa con solo unos pocos constructos.