部分評価の魔法:インタプリタからコンパイラが無料で手に入る
The Magic of Partial Evaluation
Jimmy Millerが、部分評価の美しさを実例で解き明かす。ビルド時に評価できる部分だけを評価し、動的な部分を残すこの手法を、階乗計算や簡易インタプリタ、brainfuckインタプリタに適用。インタプリタとプログラムを部分評価するとコンパイル済みプログラムが得られるというFutamura Projectionの第一段階を、実際のコード変形とともに示す。実用性より美しさを重視した自作ライブラリの紹介も兼ねる。
これが最初の驚くべき事実だ。インタプリタを取り上げ、それをプログラムとともに部分評価すると、コンパイル済みのプログラムが得られるのだ。
HNでの議論
25- TuringTest
> 私にとって、最も美しいソフトウェアとは、プログラミング言語の本質について何かを明らかにしてくれるものです。
関数型プログラマーが、コンピュータプログラムとは入力データをガリガリと処理して結果を出す機械だという学校で教わる比喩を超えて、プログラミング言語が人間の思考を象徴的に表現するものとして実際にどう機能するかについての理解を進化させる瞬間が3つあります。
1つ目は、再帰を本当に理解し、関数がそれ自身で(呼び出しごとに異なるパラメータで)定義できる仕組みを理解したときです。
2つ目は、Prologの変数の単一化やHaskellの遅延評価を発見し、プログラムが無限ループでハングすることなく無限のデータ構造を表現できることを知ったときです。
3つ目は、あらゆる命令型言語の振る舞い(マイクロプロセッサのデータパスの動作に至るまで)が、純粋関数型の書き換え言語(破壊的代入やセル状態の変更なし)で完全に表現できることを学んだときです。
これらの洞察により、すべてのプログラミングパラダイムにはシンボル処理という共通の性質があり、プログラムの実行時動作について「真の記述」は存在しないこと、つまり実行中のプログラムの命令型、関数型、論理型の見方はすべて等価な表現であることに気づかされます。
- artrax
私たちはこれをC++ライブラリとして構築し、ストリーム処理エンジンのクエリコンパイルを行っています。
https://github.com/nebulastream/nautilus
これにより、演算子や関数をLLVM IR DSL(または類似のもの)で記述する必要なく実装できます。代わりに、ラッパー型(およびその戻り値)に対して関数を記述し、C++でオーバーロード可能なものは何でもオーバーロードできます。
ラッパーはいくつかのC++の値からインスタンス化できます。その場合、ラッパーはすべてをこの値に転送するだけであり、エージェント以前の時代にはデバッグに便利でした。
しかし、そのようなラッパーをトレーサーとしてインスタンス化することもでき、関数評価の結果はトレースになります。
制御フローについては、ラッパー型がboolとして評価されるたびに記録し、最初はtrueを返し、一方の分岐の終わりに達したら例外を投げて先頭に戻り、最初からやり直しますが、今度はfalseと評価します。
得られたトレースはLLVM IRに変換してコンパイルしたり、例えばwasmで実行したりできます。
- apignotti
私たちは数年前にC++ -> JavaScript/WebAssemblyコンパイラ(Cheerp)で同様の概念を実装しました。それは素晴らしい挑戦でした。
https://labs.leaningtech.com/blog/reducing-webassembly-size-...