An Extension of Shortcut Deforestation for Accumulative List Folding

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2002-09-01

著者

• Glueck R

  Presto Japan Science And Technology Corporation

• Gluck Robert

  早稲田大学理工学部情報学科

• Kakehi K

  Nagoya Univ.

• Gluck Robert

  Presto Japan Science And Technology Corporation

• KAKEHI Kazuhiko

  the Graduate School of Information Science and Technology, The University of Tokyo

• FUTAMURA Yoshihiko

  the School of Science and Engineering, Waseda University

• Futamura Y

  The School Of Science And Engineering Waseda University

関連論文

• 再帰プログラム部分計算のための停止性判定法
• An Extension of Shortcut Deforestation for Accumulative List Folding
• Recursion Removal and Introduction Using Assignments

スポンサーリンク