A Fully Automatic Generator of Short Cut Fusion Rule Pragmas for User-Defined Data Types

Chris Savcak

Modular program construction is an integral part of any reasonable software development process. One widely-applicable way to achieve modularity in functional languages is to construct programs as ``pipelines" of small, generally applicable components. Each component in such a pipeline produces a data structure as its output, and this data structure is consumed by the next component in the pipeline. Unfortunately, modular programs are often less efficient than corresponding non-modular ones: The data structures which ``glue" their components together must literally be constructed, traversed, and discarded --- even when they play no essential role in a composition. Short cut fusion is one technique for improving the efficiency of modular programs by eliminating ``gluing" data structures. It makes essential use of a so-called fold/build fusion rule for each datatype. In this project we have constructed a tool which lets the user avoid the difficult and error-prone process of writing fold/build rules by hand. The tool allows the user to instead input a collection of datatype declarations, and automatically generates fold/build rules for them. The rules are produced in a form suitable for inclusion as pragmas, thus making it possible to automatically improve functional programs using short cut fusion.