The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O desmatamento é uma técnica bem conhecida de transformação de programas que elimina estruturas de dados intermediárias que são passadas entre funções. Um de seus pontos fracos é a incapacidade de programas de desmatamento utilizando parâmetros acumulativos. Mostramos como certos tipos de listas intermediárias produzidas pelo acúmulo de parâmetros podem ser desmatados. Neste artigo apresentamos uma variante acumulativa de dobrar, сhamado rdlof, e mostre a composição das funções definidas por dobrar e rdlof. Como um exemplo simplificado de dobrar e rdlof, examinamos então dmap, uma extensão acumulativa de mapa,e forneça as regras de fusão correspondentes. Embora as regras de composição associadas não possam capturar todos os problemas de desmatamento, elas podem lidar com a fusão acumuladora de funções de estilo de dobramento e de mapa de uma maneira simples. As regras para fusão de acumuladores apresentadas aqui também podem ser vistas como um esquema de composição restrito para gramáticas de atributos, o que por sua vez pode nos ajudar a preencher a lacuna entre os mundos de atributos e funcionais.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -