## An extended form of shortcut fusion with multiple applications

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