
2026/11/19 3:29
部分的評価の魔法
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
James Long は、理論的な美しさに留まらず実用的な効率性に焦点を当てて JavaScript アプリケーションの最適化を行うことを目的とした特別製の部分評価ツール「prepack」を Meta で復活させた。コア技術は、1971 年の Yoshihiko Futamura の業績に根ざしており、ビルド時にインタプリタを分析・実行して未使用の操作を取り除くことで、汎用コードを高特化したコンパイル版へ実効的に変換する。このプロセスは「最初の Futamura プロジェクション」(
partial_eval(interpreter, prog) -> compiled_prog)を実証しており、インタプリタの特殊化が特定のユースケースに対する汎用ディスパッチ機構を排除することを示している。また、プロジェクトは理論的な拡張として、第二のプロジェクション(partial_eval(partial_eval, interpreter) -> compiler)および第三のプロジェクション(partial_eval(partial_eval, partial_eval) -> compiler_generator)の探求も行っている。Long は Rust で JavaScript 用の限定的な部分評価器を実装し、各種インタプリタをテストすることで、これらの手法が汎用コードパスを排除し実行時パフォーマンスを著しく向上させられることを実証した。Graal ドキュメントから Veit Heller による学術論文、William R. Cook および Ralf Lämmel の論文まで、利用可能なリソースは多岐にわたる。この復活プロジェクトは、カスタムコンパイラジェネレータの作成へと拡張を企図しており、複雑なコンピュータサイエンス理論と開発者がビルド時間の短縮とパフォーマンス最適化を実現するために求める実用性を結びつけることを最終目標としている。本文
プログラミング言語の本質と部分評価:Futamura プロジェクションの世界へ
美しいソフトウェアとプログラミング言語
- 理念
- 美しさというだけで実用性がなくても構いません。
- **「美しき」**計算系システムの動作には、今も魅力があります。
- 最も美しいソフトウェアとは、プログラミング言語の本質を明らかにするものです。
- プログラミング言語こそが執着の対象であり、新たな言語を導入できない問題はありませんでした。
- プログラム言語レベルでの解決は、メタな問題そのものを解くことに他なりません。
- 特定の問題解決ではなく、「一斉に一つのクラスの問題をどう解決するか」という問いへ一段引き戻します。
- 結論
- 言語の本質を見直すと、同時に計算そのものを見直すことになります。
部分評価(Partial Evaluation)とは?
- 定義
- インタプリタやコンパイラの世界において、インタプリタとコンパイラの両方の利点を得る技術です。
- コンパイラを無料で手に入れるアプローチの一つです。
- 歴史的背景
- James Long が
(Meta)という JavaScript 用の部分評価器を復活させましたが、実用性の優先で「美しさ」が欠けていました。prepack - その失望から著者が再考し、美しさを重視した取り組みを開始しました。
- James Long が
手動による部分評価の仕組み
- 概念
- **「ビルド時に評価できるプログラムの一部のみを実行し、そのほかは残しておく」**技術です。
- コンパイル時にコードの一部を直接実行し、結果を返します。
- 静的なケース(自明な例)
function factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1); } // factorial(5) の場合、実行時の動作不要 // コンパイル時に展開:5 * (4 * (3 * (2 * 1))) - 動的なケース(本質的な還元)
function power(base, exponent) { if (exponent === 0) return 1; return base * power(base, exponent - 1); } // power(process.argv[2], 5) の場合 // 再帰呼び出しは消滅し、以下のように還元される: // process.argv[2] * (process.argv[2] * ... ) * 1 - 効果
- 再帰関数呼び出しを可能限り展開し、残るのはコードの純粋に動的な部分だけになります。
コアとなる計算例:インタプリタと式の評価
- 単純な算術インタプリタ
function calculate(expr) { if (typeof expr === "number") return expr; switch (expr[0]) { case "+": return calculate(expr[1]) + calculate(expr[2]); case "-": return calculate(expr[1]) - calculate(expr[2]); case "*": return calculate(expr[1]) * calculate(expr[2]); case "/": return calculate(expr[1]) / calculate(expr[2]); default: throw new Error("Unknown operator"); } } // 静的な式:calculate(["+", 1, ["*", 2, 3]]) -> 7 (完全評価可能) - 部分評価の過程
- 未知の値が含まれていても、既知の部分(
,1
,2
)はビルド時に評価され、残りの動的な部分のみが残ります。3calculate(["+", 1, ["*", 2, 3]]) ↓ 1 + (calculate(2) * calculate(3)) ↓ 1 + (2 * calculate(3)) ↓ 1 + (2 * 3) ↓ 7
- 未知の値が含まれていても、既知の部分(
Brainfuck インタプリタからコンパイラへ
- 動的な Brainfuck インタプリタ
- 入力(
コマンド)を必要とするプログラムに対しても部分評価が可能です。,
- 入力(
- 特殊化の結果
partial_eval(interpreter, prog) -> compiled_prog- インタプリタにプログラムを与えて部分評価することで、そのプログラムのコンパイル済みコードが得られます。
- 具体例
- Brainfuck の「Hello World」プログラムを入力すると、以下のようなコンパイル済み関数が生成されます:
function main(b) { let a; // 入力処理と文字コードの変換がビルド時に固定される a = (a & 255) + 24 & 255; return String.fromCharCode(a); } - 意義
- 「インタプリタを完全に排除でき」、パフォーマンスが向上します。
プロジェクション(Futamura Projection)
第一の投影:インタプリタからコンパイラへ
- 式
partial_eval(interpreter, prog) -> compiled_prog - 意味
- 汎用的なインタプリタに特定のプログラムを適用して特殊化します。
- インタプリタとコンパイラを書く作業は本質的に異なるため、この手法で容易にコンパイラを作れます。
- スキーマ検証の例
// スキーマ定義のみで存在する場合 function validateUser(value) { ... } // 部分評価を適用すると、専用関数に変換されパフォーマンスが向上(5 倍) // schema の値自体はランタイムで動くため、オンザフライコンパイルが必要。
第二の投影:特殊化器自身を特殊化する
- 式
partial_eval(partial_eval, interpreter) -> compiler - 仕組み
- 汎用的な特殊化器自体を入力として与えることで、「専用インタプリタファクトリ」(コンパイラ生成関数)を得ます。
- 具体例
- 単純な命令セットを持つ仮想マシン
を入力とします:interp
function interp(program, io) { // prompt や print の実行ロジックを含むインタプリタ }- これを部分評価すると、汎用的なディスパッチ機構がなくなり、以下のコンパイラ
が生成されます:compile
function compile(program) { // program を直接処理し、コードジェネレータを使って出力する // io.prompt() や io.print() の呼び出しを静的に記述へ置き換える }- 結果として、インタプリタ特有のオーバーヘッドを排除した効率的なコードが得られます。
- 単純な命令セットを持つ仮想マシン
第三の投影:コンパイラ生成器へ
- 式
partial_eval(partial_eval, partial_eval) -> compiler_generator - 到達点
- 「あらゆるインタプリタに対してコンパイラを生成する汎用的関数」を手に入れます。
- これが計算機の理論において、思考の曲がり角(Mind Bending)となります。
特殊化器としての部分評価
- 特殊化(Specializing)の本質
- プログラムを「汎用版」から「特定の単一入力を前提とした専用版」へ変換することです。
- パターンマッチングの例:
// 汎用パターン "a*b*c" function matchesAStarBStarC(text) { let i = 0; while (text[i] === "a") i++; while (text[i] === "b") i++; return text[i] === "c" && i + 1 === text.length; }
探究のための試行錯誤(Playing With It)
- 現状の取り組み
- JavaScript 用の部分評価器を実装し、Rust などへの移植や多言語対応を進めています。
- 第二および第三の投影も部分的に実働を試みています。
- アプローチ
- **「実用性」を優先せず、「計算の面白く興味深い側面」**を探究してください。
- どのような入力を与え、どんなコードが出力されるかを楽しむことが重要です。
- 関連リソース
:WebAssembly 用の部分評価器weval- Chris Fallin の「JavaScript を Wasm にコンパイルするシリーズ」第 3 部(部分評価)
- Veit Heller の「First Futamura Projection」
- GraalVM ドキュメントの「Truffle における部分評価」
- 元英語版からの翻訳:Yoshihiko Futamura(1971 年)の論文「計算過程の部分評価 — コンパイラ生成器へのアプローチ」
- Neil D. Jones らによる「Partial Evaluation and Automatic Program Generation」
- William R. Cook と Ralf Lämmel の「オンライン部分評価への入門」