Shortcut fusion rules for the derivation of circular and higher-order monadic programs

• Type: Article in International Conference Proceedings Book
• Date: 2009

Authors

Pardo, A (Author) Other; Joao Paulo Fernandes (Author) Other; Saraiva, J (Author) Other

Conference proceedings International

Title: Proceedings of the 2009 ACM SIGPLAN Symposium on Partial Evaluation and Program Manipulation, PEPM'09

Pages: 81-90

2009 ACM SIGPLAN Symposium on Partial Evaluation and Program Manipulation, PEPM'09

Savannah, GA, 19 January 2009 through 20 January 2009

Indexing

Scopus - 7 Citations

Other information

Authenticus ID: P-007-QKD

DOI: 10.1145/1480945.1480958

Abstract (EN): 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, 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 communicate 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: we derive monadic circular p ograms from strict ones, maintaining the global effects. Later, the circularities in the derived programs are traded by highorder definitions, using a well-known program transformation technique. We finally obtain very efficient deforested programs. An important feature of our extensions is that they can beuniformly defined for a wide class of data types and monads, using generic calculation rules. ©2009 ACM.

Language: English

Type (Professor's evaluation): Scientific