For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Extension of Shortcut Deforestation for Accumulative List Folding
Kazuhiko KAKEHI Robert GLUCK Yoshihiko FUTAMURA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/09/01
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>>
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.