An Extension of Shortcut Deforestation for Accumulative List Folding

Kazuhiko KAKEHI  Robert GLUCK  Yoshihiko FUTAMURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.9   pp.1372-1383
Publication Date: 2002/09/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory and Models of Software
functional programming,  deforestation,  accumulating parameter,  attribute grammars,  list processing,  

Full Text: PDF>>
Buy this Article

Deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. One of its weaknesses is the inability to deforest programs using accumulating parameters. We show how certain kinds of intermediate lists produced by accumulating parameters can be deforested. In this paper we introduce an accumulative variant of foldr, called rdlof, and show the composition of functions defined by foldr and rdlof. As a simplified instance of foldr and rdlof, we then examine dmap, an accumulative extension of map, and give the corresponding fusion rules. While the associated composition rules cannot capture all deforestation problems, they can handle accumulator fusion of fold- and map-style functions in a simple manner. The rules for accumulator fusion presented here can also be viewed as a restricted composition scheme for attribute grammars, which in turn may help us to bridge the gap between the attribute and functional worlds.