Shortcut Fusion Rules for the Derivation of Circular and Higher-order Programs

Abstract

Functional programs often combine separate parts using interme- diate data structures for communicating results. These programs are modular, easier to understand and maintain, but suffer from in- efficiencies due to the generation of those gluing data structures. To eliminate such redundant data structures, some program trans- formation techniques have been proposed. One such technique is shortcut fusion, and has been studied in the context of both pure and monadic functional programs. Recently, we have extended standard shortcut fusion: in addition to intermediate structures, the program parts may now communi- cate context information, and it still is possible to eliminate those structures. This is achieved by transforming the original function composition into a circular program. This new technique, however, has been studied in the context of purely functional programs only. In this paper, we propose an extension to this new form of fusion, but in the context of monadic programming: