部分的な評価

コンピューティングにおいて、部分評価は、特殊化によるさまざまな種類のプログラム最適化のための手法です。最も簡単な応用は、同じ動作を保証しながら、元のプログラムよりも高速に実行される新しいプログラムを作成することです。

コンピュータプログラム prog は、入力データを出力データに マッピングしたものとして考えられます。

$${\displaystyle prog:I_{\text{static}}\times I_{\text{dynamic}}\to O,}$$

ここで、静的データ は、コンパイル時に既知の入力データの部分です。 ${\displaystyle I_{\text{static}}}$

部分評価は、コンパイル時にすべての静的入力を事前計算することでに変換します。 は「残差プログラム」と呼ばれ、元のプログラムよりも効率的に実行されるはずです。 部分評価の動作はに「残差化」すると言われています。 ${\displaystyle \langle prog,I_{\text{static}}\rangle }$${\displaystyle prog^{*}:I_{\text{dynamic}}\to O}$${\displaystyle プログ^{*}}$${\displaystyle プログ}$${\displaystyle プログ^{*}}$

^{1970年代に二村吉彦氏[1]}によって初めて説明された部分評価の使用例として特に興味深いのは、progがプログラミング言語のインタープリタである場合である。

I _{static が}そのインタープリタ内で実行するように設計されたソース コードである場合、このデータ/プログラムに関してインタープリタを部分的に評価すると、prog * が生成されます。これは、そのソース コードのみを実行し、インタープリタの実装言語で記述され、ソース コードの再提供を必要とせず、インタープリタとソースの元の組み合わせよりも高速に実行されるインタープリタのバージョンです。この場合、prog * は実質的にI _staticのコンパイルされたバージョンです。

この手法は第一二村図法として知られており、次の 3 つがあります。

1. 指定されたソース コードに対してインタープリターを特化して、実行可能ファイルを生成します。
2. スペシャライザーをインタープリター用に特殊化 (#1 で適用) して、コンパイラーを生成します。
3. スペシャライザーをそれ自身に特化することで (#2 で適用)、任意のインタープリターを同等のコンパイラーに変換できるツールが生成されます。

これらは1971年に二村によって日本語で記述され^[2]、1983年に英語で記述されました^[3]。

• コンパイル時の関数実行
• メモ化
• 部分適用
• 実行時アルゴリズムの特殊化
• s _mn定理
• 強度低下
• テンプレートメタプログラミング