こんにちは、habrachelovek。 今日は、コンピューターサイエンスのいくつかの基本的なことについて説明します。部分計算、3つのFutamuraプロジェクション、スーパーコンパイルです。

1.コードに移動します

-- , x y ()
power xy =
case y of
0 → 1
1 → x
_ → x * (power x (y - 1))



この関数を次のように使用するとします。

-- ,
rectangleArea side = power side 2


この小さな例は、プログラミングにおける最も重要なパターンである抽象化を明確に示しています。

この例のように、ほとんどの場合、特別な特別な場合に抽象化を使用しますが、未使用の部分は必然的に計算のオーバーヘッドを引き起こします。

たとえば、お気に入りのWebフレームワークを考えてください。 しかし、そのコードのどの部分がアプリケーションで本当に役立つ仕事をしていますか？

この質問は、多くの経験の浅いプログラマーにとって文字通りクレイジーであり、時期尚早な最適化、抽象化の否定、およびその他の愚かなことに従事し始めます。

しかし、抽象化の使用はオーバーヘッドを伴う必要はありません。 重い全能フレームワークを使用するコードは、手動で記述されたアドホックコードよりも遅く実行する必要はありません。

パーシャルコンピューティングは、抽象化によるオーバーヘッドを完全に排除する強力な手法です。 プログラムの速度を大幅に向上させる圧倒的な数の最適化は、プログラムの部分計算の特殊なケースです。 簡単な例：

var someMagicNumber = 2^32


ほとんどすべての最新のコンパイラは、コンパイル中に式を書き直すことでこの式を単純化（および単純化）できるため、コードを実行するときに何度も計算する必要はありません。

var someMagicNumber = 4294967296


これは、部分計算の最も単純な例です。 この最適化中にプログラムの一部が実行されて結果が保存され、他の部分は変更されないため、この用語がそう呼ばれます。

最初の例を正方形の領域で部分的に計算してみましょう。 コンパイラの代わりに自分を想像してください。 コンパイラーは、 べき乗関数が常にパラメーターy = 2でこの場所で計算されることを知っています。 したがって、このパラメータに特化して、部分的に計算できます。

特殊化、ステップ1。自由パラメーターyの代わりに定数2を代入します。

-- , x y ()
power2 x =
case 2 of
0 → 1
1 → x
_ → x * (power x (2 - 1))


ステップ2.不合理な分岐0 == 2および1 == 2を破棄して、case-ofを計算します。

-- , x 2
power2 x = x * (power x (2 - 1))


ステップ3.式（2-1）を計算します。

-- , x 2
power2 x = x * (power x 1)


ステップ4. y = 1をべき乗関数に代入すると、次のようになります。

-- , x 2
power2 x = x * x


確かに、すでにインライン化手法との類似性を引き出しています-C / C ++でおなじみの関数置換です。 これらも部分的な計算です。

2.二村の予想

二村佳彦教授はかつて、部分計算の文脈でのプログラムの解釈を空想していました。 それは言わなければならない、それはその完全な屋根カバーと言わないまでも、非常に面白いことが判明した：

部分的な計算（プログラムの特殊化）を行う特定のマジック関数があるとします。

specialize (program, data) : specialized_program


たとえば、上の例の関数function powerをspecializeとデータ「y = 2」に入れると、関数power2が得られます。 とても簡単です。

また、特定の言語のインタープリター、たとえば、アセンブラー（ho-ho）で記述されたPHPインタープリターがあります。

php_eval (php_code) : data


入力にはphpコードの行があり、出力には計算の結果があります。 珍しいことでもありません。

注意、質問。 これを行うとどうなるかを考えてください。

specialize (php_eval, php_code) ?


アセンブラーのインタープリターphpと文字列をphpコードと混合します。 結果は、phpプログラムと同じことを行うasmプログラムです。 これは、phpコードをasmにコンパイルしたことを意味します！

したがって、 Futamuraの最初の投影 ：コンパイルは、インタープリターをインタープリタープログラムのコードに特化したものです。

compiled_php_code = specialize (php_eval, php_code)


おかしいですね。

もっともっと。 実行するとどうなりますか：

specialize (specialize, php_eval) ?


アセンブラーでPCPの専門家と通訳を混ぜます。 結局のところ-任意のphpコードを入力できるプログラムで、アセンブラーコードに変換されます。

PHP インタープリターと魔法のスペシャリストしかいないため、PHPコンパイラーを誕生させることができました！

これは二村の2番目の予測です。コンパイラーは、インタープリターコードによる専門家の専門化です。

php_compiler (php_code) = (specialize (specialize, php_eval)) (php_code)


私の頭は少し痛くなり始めましたが、結果は何ですか-コンパイラはインタプリタから作られました！ そして、それだけではありません...このようにしましょう：

specialize (specialize, specialize)


OMFG、それは何ですか？ これはコンパイラジェネレータです。 入力にインタプリタを与え、出力にコンパイラを取得します。

make_compiler (interpreter) = (specialize (specialize, specialize)) (interpreter)


これは二村の3番目の投影です 。

3.スーパーコンパイル、メタ計算

部分的な計算では、既知のデータをプログラムに代入することでコードを削減できます。 しかし、コードをさらに最適化できるさらに高度な手法があり、部分計算はその一部であるスーパーコンパイルです。

プログラムの実行を数学的にシミュレートし、このモデルを使用してより効率的なプログラムを生成するコンパイラは、 監視コンパイラと呼ばれます。

この用語（および関連する研究）の著者が同胞であるValentin Turchinに属しているのは興味深いことです。 また、スーパーコンパイルの概念を示すRefal言語を開発しました（この言語は非常に古く、書き換えの用語に基づいています）。

スーパーコンパイルは、プログラムの「抽象解釈」とも呼ばれます。 Turchinでは、これは英語の出版物では「運転」という用語で示されます。

実行中、コンパイラはプログラムプロセスのツリーを構築します。これは、考えられるすべてのプログラム状態とそれらの間のエッジ遷移のグラフです。

コンパイラは、いわば、プログラムのプロセスを理解しようとしています。 簡単な例を使って説明します。

frobnicate X =

case X of

true → case X of
true → garply
false → xyzzy

false → case X of
true → plugh
false → garply


このコードで奇妙なものを見つけませんか？ Xの値については、アルゴリズムはxyzzyまたはplughに到達しません。 アルゴリズムを精神的にスクロールすると、これが表示されます。 この結論に至った経緯を考えてください。結局のところ、スーパーコンパイラーはまったく同じように機能します。

プロセスのツリーを構築します。

X
→ true -- X == true

case true of
true → garply
false → xyzzy

→ false -- X == false

case false of
true → plugh
false → garply


分岐の部分計算ケース：

X
→ true → garply
→ false → garply


したがって：

frobnicate X = garply


この技術をJavaに実装する試みがありました。
www.supercompilers.com/white_paper.shtml

そして、最近、Haskell（Supero）の場合：
www-users.cs.york.ac.uk/~ndm/supero/

おそらく、一部の読者は、部分的な計算とスーパーコンパイルを使用して、すべてのプログラムを完全に最適化する特定のコンパイラをすでに想像しています。 しかし、この問題を解決することは不可能です-それは解決できない問題のクラスに属しています 。

実際には、プログラムのプロセスツリーは無限になり、インテリジェントな処理には大きすぎます。 これは、数千万行のコードを持つ大規模な商用アプリケーションはもちろんのこと、小さなプログラムでさえ分析しようとすると発生します。

この問題を回避するためのさまざまな手法があります。 一般化 -無限ツリーの一般化、折りたたみ（コードの折りたたみ）-同じ計算ブランチの一般化。

また、これらの手法の実装には多くの問題領域があります。たとえば、いつ一般化するか、いつしないかを判断するのは必ずしも容易ではありません。 sayingにもあるように、悪魔は細部に宿っています。

4.反転によるプログラミング

プログラムのスーパーコンパイルは興味深い副作用をもたらします-論理プログラミングの問題を解決する（ Prologを思い出してください）、定理を証明し、 計算を逆にすることができます。

関数と抽象的な計算グラフ（プロセスツリー）の多くの入力と出力があるため、特別な場合には計算を逆にすることができます。

次のタスクがあるとします。「abcd」という文字列で、2文字長のすべての部分文字列を検索します。

bにaが含まれる場合にtrueを返す関数（strstr ab）があります。 次に、反転を適用してソリューションを書き留めます。次のようになります。

>> [x | where (strstr x "abcd"), (length x) == 2]
["ab", "bc", "cd"]


すぐに、関数型プログラミング言語のパターンマッチングの手法と関連があります。 実際、これは事実です-アルゴリズムの反転は、抽象的なパターンマッチングの鍵です。

結論の代わりに

ここにそのような記事があります、ハーバーマン。 彼女があなたがプログラムの解釈、最適化、コンパイルについて異なる角度で見るのを手伝ってくれたことを願っています。

追伸： 良い利益のためにHaskellを学ぶ！