Construcción y optimización de programas en Fork Álgebras

Abstract

La creciente importancia de los factores críticos en el software hace que la utilización de métodos formales de desarrollo sea cada vez más frecuente. En este contexto, la construcción rigurosa de programas, concebida como un “álgebra de la programación” [BdM97] o bien como un “cálculo de programas” [FBH 97], constituye uno de los elementos de mayor relevancia, en al medida que provee técnicas, métodos y, más aún, estrategias generales que posibilitan obtener programas correctos por construcción a partir de especificaciones formales o semiformales. En este trabajo se presentan Estrategias de Construcción de Programas basadas en la Teoría de Primer Orden de las Fork Álgebras. En este contexto se describen estrategias, usuales en la Programación en Lógica y Funcional, como “tupling” y “generalización” que resultan de gran utilidad tanto como herramientas de solución de problemas, como técnicas de diseño de algoritmos y también como métodos generales de optimización de programas recursivos. Se analizan condiciones suficientes para la aplicación de estas estrategias a expresiones algebraicas que caracterizan algoritmos genéricos (Es decir, clases de algoritmos) y se presentan varios ejemplos de aplicación de las mismas.