Título: Extensiones a la regla de fusión de tipo "shortcut"

Marco de Trabajo: Investigación

Área de desarrollo: Métodos Formales

Autor: Alberto Pardo

Contacto: pardo@fing.edu.uy

Día: VIERNES

Hora: 11:45

Palabras Claves: fusión, deforestación, programación funcional

Resumen:
Las técnicas de optimización de código son muy importantes en programación funcional. En este tipo de lenguajes la idea es que el programador pueda escribir su código sin preocuparse por aspectos relacionados con la ejecución del mismo, como por ejemplo, gerenciamiento de la memoria, eficiencia de algunas construcciones, etc. Si es que existe alguna posibilidad de optimizar el código, el programador funcional espera que la dicha optimización sea relizada por el compilador. Por supuesto esto no incluye aspectos relacionados con la complejidad de los algoritmos implementados.
Un programa funcional consiste de un conjunto de definiciones de funciones que reciben ciertas estructuras de datos como entrada y retornan otras como salida. Dichas funciones se suelen construir como la composición de funciones relativamente simples y sencillas de escribir. Los programas así definidos tienden a ser más modulares, pero su eficiencia puede verse afectada en forma significativa por el uso sistemático de la composición de funciones. Cada composición implica la construcción de una estructura de datos intermedia cuyos valores deben ser alojados en memoria, recorridos y finalmente descartados, requiriendo por lo tanto tiempo adicional de procesamiento, espacio de memoria para alojar nodos de la estructura y frecuentes llamadas al “garbage collector”.
Existen técnicas de transformación de programas cuyo objetivo es la eliminación de aquellas estructuras intermedias que no jueguen un rol esencial en la computación. Esto es, se desea transformar el código original a uno equivalente en donde se intenta sustituir las composiciones de funciones por definiciones que mezclan los códigos de las funciones involucradas. A estas técnicas de transformación de programas se las conoce como fusión o deforestación.
En esta charla hablaremos de una técnica de fusión, conocida como "shortcut fusion", presentaremos una extensón a la regla estándar de "shortcut fusion" y mostraremos aplicaciones. En particular, gracias a la regla de fusión extendida ha sido posible definir la fusión de programas funcionales con efectos colaterales y la derivación de programas circulares (tanto puramente funcionales como con efectos).