Un sistema ampliado de desplegado/plegado para la síntesis de programas funcionales

Abstract

Proponemos una extensión, para la síntesis de funciones, del sistema de transformación de desplegado/plegado. Se amplía no tanto el lenguaje de programación funcional como el sistema de transformación. El lenguaje ampliado permite relaciones (Es decir, restricciones) que expresan precondicinoes y poscondicinoes, pero que no pueden usarse para construir funciones ejecutables, sino que su uso está limitado al proceso transformador. El sistema de transformación también se amplía para tratar restricciones e igualdades generales, resultando un sistema de cinco reglas, potente pero sencillo. Hemos estudiado principalmente su aplicación a la síntesis de funciones inversas de otras existentes. El sistema resulta especialmente útil y natural cuando se combina con una forma poderosa de especificar inversas de funciones, llamada patrones generalizados. En el papel ilustramos estas ideas con la aplicación del sistema a varios problemas, destacando la síntesis de una función que reconstruye un árbol binario a partir de sus recorridos en preorden y en inorde.