An extended form of shortcut fusion with multiple applications
Alberto Pardo
Instituto de Computación
Universidad de la República
Tuesday, 24 March 2009, 11:00 (note the unusual weekday and time)
Cybernetica Bldg (Akadeemia tee 21), room B126
Slides from the talk [pdf]
Abstract: Functional programs often combine separate parts using intermediate data structures for communicating results. These programs are modular, easier to understand and maintain, but suffer from inefficiencies due to the generation of those gluing data structures. To eliminate such redundant data structures, some program transformation techniques have been proposed. One such technique is shortcut fusion.
In this talk, we will present an extended form of shortcut fusion such that, in addition to intermediate structures, the program parts may now communicate context information or even effects, and it is still possible to eliminate those structures. We show that this extension can be used in multiple cases, such as, the elimination of intermediate structures in compositions of monadic programs, the derivation of purely-functional and monadic circular programs, and the derivation of purely-functional and monadic higher-order programs.
An important feature of the extension to be shown is that, similarly to standard shortcut fusion, it can be uniformly defined for a wide class of data types and monads, using generic calculation rules.
(Joint work with João Fernandes, João Saraiva and Cecilia Manzino.)
Tarmo Uustalu
Last update 24.3.2009