An Extension of Shortcut Deforestation for Accumulative List Folding
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E85-D No.9 pp.1372-1383
- Publication Date
- 2002/09/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Theory and Models of Software
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuhiko KAKEHI, Robert GLUCK, Yoshihiko FUTAMURA, "An Extension of Shortcut Deforestation for Accumulative List Folding" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 9, pp. 1372-1383, September 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_9_1372/_p
Copy
@ARTICLE{e85-d_9_1372,
author={Kazuhiko KAKEHI, Robert GLUCK, Yoshihiko FUTAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={An Extension of Shortcut Deforestation for Accumulative List Folding},
year={2002},
volume={E85-D},
number={9},
pages={1372-1383},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - An Extension of Shortcut Deforestation for Accumulative List Folding
T2 - IEICE TRANSACTIONS on Information
SP - 1372
EP - 1383
AU - Kazuhiko KAKEHI
AU - Robert GLUCK
AU - Yoshihiko FUTAMURA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2002
AB - 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.
ER -
English
