Título: Fusion en presencia de acumuladores

Marco de Trabajo: Maestría

Área de desarrollo: Métodos Formales

Autor: Mónica Martínez

Contacto: mmartine@fing.edu.uy

Día: VIERNES

Hora: 11:15

Palabras Claves: Acumulaciones, Fusión de programas, Deforestación, Programación Funcional

Resumen:
En programación funcional es común escribir los programas como composición de funciones relativamente sencillas. Dada una composición de la forma cons . prod, a cons se le suele decir la función consumidora y a prod la función productora. Esta forma de escribir los programas tiene las ventajas asociadas a un tipo de programación modular, como ser claridad y fácil mantenimiento, pero en muchos casos los programas obtenidos tienen problemas de eficiencia, respecto a tiempo de ejecución y cantidad de memoria requerida, debidos a la construcción de las estructuras de datos intermedias necesarias para la comunicación de datos entre las funciones que intervienen en las composiciones. Definiciones más eficientes pueden ser obtenidas por la aplicación de técnicas de transformación de programas, conocidas como fusión o deforestación, las cuales apuntan a la eliminación de las estructuras de datos intermedias. El objetivo es que el programador pueda continuar escribiendo sus programas en forma composicional y que al mismo tiempo se pueda generar un código equivalente y más eficiente en forma automática.
En la actualidad existen diferentes métodos bien conocidos que permiten realizar con éxito estas transformaciones para un gran conjunto de funciones. Sin embargo aún persiste una clase de funciones para las cuales no se ha encontrado una técnica que permita realizar la fusión en forma eficaz en todos los casos. Ese es el caso, por ejemplo, de las funciones que construyen sus resultados en parámetros adicionales, llamados parámetros de acumulación. Para estas funciones la aplicación de las técnicas de fusión clásicas no consiguen alcanzar los parámetros de acumulación de las funciones productoras, lo que provoca que se mantenga en parte la generación de la estructura de datos que se pretende eliminar. Si bien aún es un problema abierto para el cual no se ha encontrado una solución general, existen diversas propuestas y abordajes que son capaces de resolverlo con distinto nivel de éxito y sencillez para ciertos grupos particulares de funciones. Dos ejemplos representativos de estas propuestas son el método de fusión algebraica [KN06] y el método que hace uso de programas circulares [Voi04].
En el presente trabajo realizamos un estudio de la fusión de funciones con acumuladores desde dos puntos de vista.
En primer lugar, analizamos un esquema de programa llamado afold [Par03], que captura cierta clase de funciones recursivas con acumuladores, y realizamos una modificación al mismo para ampliar el conjunto de funciones que es capaz de capturar.
En segundo lugar, nos concentramos en la propuesta de una técnica de fusión para funciones con acumuladores basada en el abordaje conocido como "shortcut fusion" [GLJ93] tal que contemple el caso en que la función productora genera sus resultados utilizando parámetros de acumulación, situación que no es considerada en la propuesta estándar de "shortcut fusion". La técnica a presentar tiene la característica de ser sencilla, fácil de utilizar y de automatizar. Junto a la propuesta esta nueva técnica de fusión realizamos una serie de pruebas con ejemplos concretos con el objetivo de obtener comparaciones del tiempo y espacio requerido por los programas originales y los transformados, permitiendo así identificar grupos de programas para los cuales la aplicación de la técnica resulta efectiva.
Un aspecto importante a mencionar es que tanto la técnica de fusión asociada al esquema afold como la basada en "shortcut fusion" tienen como característica el hecho de que son genéricas, en el sentido que pueden ser definidas de manera uniforme para una amplia clase de funciones y tipos de datos.
Referencias
[GLJ93] - Andrew Gill, John Launchbury, and Simon L Peyton Jones. A short cut to deforestation. In Functional Programming Languages and Computer Architecture, FPCA’93, page 223-232. ACM Press, 1993.
[KN06] - Shin-Ya Katsumata and Susumu Nishimura. Algebraic fusion of functions with an accumulating parameter and its improvement. In 11th ACM SIGPLAN International Conference on Functional programming, ICFP’06, pages 227-238. ACM Press, 2006.
[Par03] - Alberto Pardo. Generic accumulations. In IFIP TC2/WG2.1 Working Conference on Generic Programming, IFIP Series, volume 243: Generic Programming, pages 49-78, Kluwer Academic Publishers, 2003.
[Voi04] - Janis Voigtländer. Using circular programs to deforest in accumulating parameters. Higher-Order and Symbolic Computation, 17:129-163, 2004.