• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)Vol. 43. No. SIG 3(PRO 14). Mar. 2002. 情報処理学会論文誌:プログラミング. 発表概要. 累積変数を用いるリスト 処理関数とその融合法 筧. 一. 彦†. Robert Glueck††. 二. 村. 良 彦†††. 関数の間で渡される中間データを排除する方法として,Wadler によって提案された deforestation というプログラム融合手法がよく知られている.その派生として Gill が shortcut deforestation を提 案し,これは以下の 2 点で優れたものとなっている.1 つは,変換規則が 1 つだけであり,実装が非 常に容易であること.もう 1 つが,deforestation が扱うことのできない累積変数を持った関数の融 合が可能であることである.しかしながら,変換後のプログラムの分析のしやすさという点では,現 在の累積変数に関する解決方法は必ずしも優れているとはいえない.本発表は,ある種の累積変数を 持った関数について,関数融合を可能とする方法を提案する.この方法として,まずリスト処理を行 う累積変数を持った関数を定義し,shortcut deforestation に基づいた融合法を説明する.また,こ れを簡略化した融合法も提案する.今回提案する手法は,ある特定の種類の累積変数を扱うものだが, 変換後のプログラムの分析が容易となる利点がある.関数融合については,近年属性文法に基づいた 手法が提案されており,累積変数を持った関数の融合を実現している.こうした手法との比較も行う.. An Accumulative Extension of List Manipulation Functions and Their Composition Kazuhiko Kakehi,† Robert Glueck†† and Yoshihiko Futamura††† 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, techniques 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.. ( 平成 13 年 10 月 22 日発表). † 早稲田大学大学院理工学研究科,学振特別研究員 Graduate School of Science and Engineering, Waseda University, Research Fellow of the Japan Society for the Promotion of Science (JSPS) †† 科学技術振興事業団さきがけ研究 21 PRESTO, Japan Science and Technology Corporation (JST) ††† 早稲田大学ソフトウェア生産技術研究所 Institute for Software Production Technology (ISPT), Waseda University. 88.

(2)

参照

関連したドキュメント

In the spirit of our semimartingale norm, we introduce a norm for the barriers of DRB- SDEs and provide a priori estimates for the solution of DRBSDEs based on our new barrier

In the study of dynamic equations on time scales we deal with certain dynamic inequalities which provide explicit bounds on the unknown functions and their derivatives.. Most of

[9] DiBenedetto, E.; Gianazza, U.; Vespri, V.; Harnack’s inequality for degenerate and singular parabolic equations, Springer Monographs in Mathematics, Springer, New York (2012),

We use these to show that a segmentation approach to the EIT inverse problem has a unique solution in a suitable space using a fixed point

Finally, in Section 7 we illustrate numerically how the results of the fractional integration significantly depends on the definition we choose, and moreover we illustrate the

A monotone iteration scheme for traveling waves based on ordered upper and lower solutions is derived for a class of nonlocal dispersal system with delay.. Such system can be used

, 6, then L(7) 6= 0; the origin is a fine focus of maximum order seven, at most seven small amplitude limit cycles can be bifurcated from the origin.. Sufficient

The aim of this paper is to establish a new extension of Hilbert’s inequality and Hardy- Hilbert’s inequality for multifunctions with best constant factors.. Also, we present