部分評価の紹介 An Introduction to Partial Evaluation (Neil D. Jones, ACM Computing Survey Vol.28 No.3 Sep. 1996) 発表者：神戸 基本的なアイディア 1. 2. 3. 汎用的なプログラムを様々な用途で高速 に動作させたい 用途に合わせて入力を静的な部分と動 的な部分に分割 静的な部分を事前に計算 特殊化した専用のプログラムを作成 Partial Evaluator 汎用プログラム p 静的入力 部分評価器 in1 “mix” 動的入力 特殊化済み in2 ・・・データ プログラム pin1 ・・・プログラム 出力 例：べき乗計算 2入力の元プ p = ログラム f(n, x) = if n = 0 then 1 else if even(n) then f(n/2, x)^2 else x * f(n-1, x) 静的入力n = 5について特化した1入力プログラム p5 = f5(x) = x * ((x^2)^2 Partial Evaluationの実際 Annotation：プログラムを分割してマーク Binding Analysis Partial Evaluation：評価の実行 記号計算（symbolic computation） 展開（unfolding） プログラム・ポイント特殊化(program point specialization) 定義生成(definition creation) 畳み込み(folding) Annotation 式 Eliminable： 部分評価により削除可能 Residual： 部分評価後も残留 引数 Static： 静的引数 Dynamic： 動的引数 Annotationの満たすべき条件 合同条件（congruence condition） プ ロ グ ラ ム の 適 切 な 部 分 が annotate さ れ る 。 最低限、削除可能とマークされた全ての引数と 演算については、ありえる全ての静的な入力に ついて特殊化できることが保証されること 終了条件（termination condition） 静的な入力の値に関わらず特殊化が終了するこ と（無限に沢山の関数や式が出力されない） Partial Evaluation （アルゴリズムの詳細はレジュメ） OfflineとOnline オフライン特殊化（offline specialization） Annotation→Partial Evaluationの2ステップ オンライン特殊化（online specialization） 2ステップと限らず評価中に分かった情報でさ らに特殊化 長所：特殊化後の速度効率の向上 短所：特殊化の処理時間増加、停止性 特殊化の弱点の例 例： べき乗の例でxが分かっていてもさし て高速化の足しにはならない 例： インタプリタの特殊化で生成されたプ ログラムはインタプリタの出来に左右され る。（例えば動的にサーチして変数名の束 縛を行う場合や、動的にソースを生成する 場合はターゲットでもそうなる。） 特殊化が向いている計算 時間が掛かる処理 繰り返し行われる処理 似たようなパラメタで何度も行われる処理 構造化され明快に書かれたプログラム（そ うでなければ人間だけでなく特殊化プログ ラムにとっても扱い難い） 高レベルなアプリケーション志向言語で書 かれたプログラム 例：プログラム・ジェネレーター インタプリタによる言語定義（レジュメの図5） インタプリタを静的入力、プログラムを動的入 力として特殊化 インタプリタ実装言語によるプログラムへ変換 正規表現の認識（レジュメの図6と図7） rexをインタプリタ、正規表現をソース、と考え て特殊化 与えられた正規表現（例えば(a+b)*abb）を受 理する有限オートマタになっている コンパイラとインタプリタの得失 インタプリタ プログ 小さく簡単 ラミン （一個の言語に対する動作を一 グ 度だけ考えればよい） コンパイラ 大きく難しい （ソース言語での動作と生成された ターゲット言語での動作の双方を考 えねばならない） 言語 定義 高級言語で直接に操作的意味 付けをしながら定義できる 効率 実行毎に解釈のオーバーヘッド 一般にコンパイル済みのコードは高 速に実行可。 1フェーズ目で大局的な情報を利用 して2フェーズ目のプログラム最適化 が可能 コンパイラとインタプリタ ソース・プロ グラム 実行時 入力 インタプリタ 出力 [[src]]S d = [[interpreter]]L [src, d] ソース・プ ログラム コンパイラ 実行時 入力 目的プログ ラム 出力 [[src]]S d = [[ [[compiler]]L src]]T d 例：インタプリタの特殊化 インタプリタ ソース・プロ グラム mix 実行時入力 特殊化済イ ンタプリタ 出力 例： プログラム・ジェネレータの 生成 特化されたプログラムと比べて経験上遅す ぎるために極端に一般的なプログラムは滅 多に利用されない 例： specification executers 実行可能仕様の直接性や簡潔さと、プログ ラムジェネレータ（コンパイラやパーサ）によ り生成された実行可能プログラムの効率性 を両立したい プログラム・ジェネレータの生成 （図） 汎用プログラム p cogen 静的入力 in1 動的入力 in2 pに対する Ershovの Generating Extension p-gen 特殊化済み プログラム pin1 出力 プログラム生成に関する性質 mixに成り立つ等式から導ける性質 第1二村Projection （インタプリタをあるソースに特化）： tgt = [[mix]] [int, src] 第2二村Projection （mixをあるインタプリタに特化） ： comp = [[mix]] [mix, int] 第3二村Projection （mixをmixに特化） ： cogen = [[mix]] [mix, mix] （直接mixを利用するより自己適用して作ったコンパイラやコンパイラ・コ ンパイラを利用する方が10倍程度変換が早いことが経験的に知られ ている。） プログラムの自動生成 プログラミング・スタイルの変換 メタ言語の階層 Semantic-directedなコンパイラ生成 実行可能な仕様 その他の例 パターン認識 コンピューター・グラフィクス 問い合わせ言語→特定目的の問い合わせ（他） ニューラル・ネット レイ・トレーシング→特定のシーン データベースへの問い合わせ 汎用の正規表現認識プログラム→特定の正規表現 →特定のネットワーク・トポロジーで学習を高速化 表計算 対話的な表計算プログラム→特定目的 効率と汎用性とモジュラ性 効率のよいプログラムを沢山書く 効率は悪いが汎用でパラメタ化可能なプ ログラムを1つ書く → 汎用に書いて興味のある目的に特殊化 界面でオーバーヘッドがあるけれどモ ジュール化された扱いやすいプログラム 界面が少なく効率がよいが一枚岩で扱い 難いプログラム → モジュール化して書き、特殊化によって界 面のオーバーヘッドを除去 結論 部分計算とself-applicationは多くの応用が あり、プログラム・ジェネレータの生成（コン パイラ、コンパイラ・ジェネレータ、プログラ ム変換系）に役立つ。 この分野でよく発生する問題 部分計算の停止性 入力プログラムに対する特殊化済プログラ ムの意味論的忠実性（faithfulness） 停止性、バック・トラック、結果の正当性、他 特殊化による高速化度合いの予想困難性 高速化のためのプログラム修正の困難性 今後の課題 部分評価系を利用しやすくする どの程度の高速化が可能なのかを理解する 特殊化を行う前に高速化の効果とメモリ使用量 を予測する 型付き言語における特殊化を改良する コードの爆発的増加を（自動的に）回避する インタプリタで定義されたソース言語向けに、キ チンとしたマシン・アーキテクチャを生成する 個人的なメモ 結局静的/動的の区別が問題 Binding Analysisについて調べる 型との関連を調べる
© Copyright 2024 ExpyDoc
![[TL]Editorリリースノート Ver.4.0](http://s3.expydoc.com/store/data/007460792_1-5ab3b222da6f6a27e6440f7e68f58d5f-250x500.png)
