累積変数を用いるリスト処理関数とその融合法

• Item type: Trans(1)
• 公開日: 2002-03-15
• タイトル: 累積変数を用いるリスト処理関数とその融合法
• タイトル / 言語: en
• タイトル: An Accumulative Extension of List Manipulation Functions and Their Composition
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学大学院理工学研究科，学振特別研究員
• 著者所属: 科学技術振興事業団さきがけ研究21
• 著者所属: 早稲田大学ソフトウェア生産技術研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Waseda University, Research Fellow of the Japan Society for the Promotion of Science (JSPS)
• 著者所属(英): en
• 著者所属(英): PRESTO, Japan Science and Technology Corporation (JST)
• 著者所属(英): en
• 著者所属(英): Institute for Software Production Technology (ISPT), Waseda University
• 著者名: 筧, 一彦; Robert, Glueck; 二村, 良彦
• 著者名(英): Kazuhiko, Kakehi; Robert, Glueck; Yoshihiko, Futamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 関数の間で渡される中間データを排除する方法として，Wadlerによって提案されたdeforestationというプログラム融合手法がよく知られている．その派生としてGillがshortcut deforestationを提案し，これは以下の2点で優れたものとなっている．1つは，変換規則が1つだけであり，実装が非常に容易であること．もう1つが，deforestationが扱うことのできない累積変数を持った関数の融合が可能であることである．しかしながら，変換後のプログラムの分析のしやすさという点では，現在の累積変数に関する解決方法は必ずしも優れているとはいえない．本発表は，ある種の累積変数を持った関数について，関数融合を可能とする方法を提案する．この方法として，まずリスト処理を行う累積変数を持った関数を定義し，shortcut deforestationに基づいた融合法を説明する．また，これを簡略化した融合法も提案する．今回提案する手法は，ある特定の種類の累積変数を扱うものだが，変換後のプログラムの分析が容易となる利点がある．関数融合については，近年属性文法に基づいた手法が提案されており，累積変数を持った関数の融合を実現している．こうした手法との比較も行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Wadler’s deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. Shortcut deforestation proposed by Gill is a composition technique derived from deforestation. One benefit of the latter method is to use a single simple rule, and this strategy is successful in real implementation. As another notable benefit, it can handle to deforest accumulating parameters of functions which ordinary deforestation fails. However, the current solution for accumulation is not preferable for program analysis. We show another way to tackle certain kinds of accumulation deforestation. For this we introduce list manipulation functions with accumulation, and demonstrate fusion rules based on shortcut deforestation. We also present a simplified solution for this problem. While the associated composition rules cannot capture all deforestation problems, they can handle accumulator fusion in a simple way. In terms of function composition, tech-niques based on attribute grammars has been proposed recently. Such techniques are powerful enough to be able to deal with composition of troublesome accumulating parameters. We also explain the relation and comparison with attribute grammars composition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 43, 号 SIG03(PRO14), p. 88-88, 発行日 2002-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会