部分評価の魔法
The Magic of Partial Evaluation (jimmyhmiller.com)
要約
この記事は、プログラミング言語の性質を明らかにする「部分評価」という概念について解説しています。部分評価は、プログラムの一部をビルド時に評価し、残りを動的な構造に還元する技術であり、インタープリタからコンパイラを無料で得るというFutamura Projectionの基礎となります。筆者は、この概念を探求するためのJavaScript用部分評価器ライブラリ「split-shot」を紹介しています。
全文翻訳
部分評価の魔法
ソフトウェアには、実用性に関係なく、ただ美しいだけのアイデアがいくつか存在します。同僚を説得できないとしても、なぜか心を惹かれる計算システムの働き方があります。
私にとって最も美しいソフトウェアは、プログラミング言語の本質について何かを明らかにするものです。プログラミング言語は私の情熱です。新しいプログラミング言語を導入すれば解決できない問題に遭遇したことはありません。プログラミング言語レベルで問題を解決することは、メタ問題の解決を意味します。特定の問題を解決しようとするのではなく、一歩引いて、どのようにすれば一連の問題を一度に解決できるかを問います。
そのため、プログラミング言語の本質について考え直させるようなものを見つけると、計算全体について考え直すようになります。これらの信じられないほど美しくも複雑な概念の一つに、「部分評価」という名前のものがあります。インタープリタやコンパイラに魅了されているなら、部分評価はそれらがどのように関連しているか、そしてどのようにしてコンパイラを無料で手に入れることができるかを教えてくれるでしょう。
部分評価 イージーモード
部分評価はしばらく私の心を捉えてきました。しかし、この件全体が浮上したのは、James LongがMetaの部分評価器であるprepackを復活させたと発表したときでした。prepackについて最初に聞いたとき、私はこのプロジェクトに大きな期待を寄せていましたが、残念ながらがっかりしました。この復活は、それと同じ夢を再び明るみに出しました。しかし残念ながら、当初の目的と同様に、prepackは美しさのためではなく、実用性のために設計されたものではありませんでした。そこで、私は自分の努力を新たにすることにしました。
はい、ある意味ではこれは私がリリースする自身のライブラリを宣伝する投稿です。しかし、それは使ってほしいからではありません。それは、私がこれほど美しいと感じるアイデアを試すことができるからです。この投稿はそれについてです。
部分評価を手作業で行う
以下のコードを考えてみましょう。
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] * (process.argv[2] * (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]]);
ここでは、算術をサポートする言語の非常に単純なインタープリタがあります。上記の式について、どのように「部分的に」評価を開始できるかを考えることができるはずです。(この場合、完全な評価が可能です。)この種の部分評価がまだピンとこない場合は、理解を助けるためにステップを以下に示します。
calculate(["+", 1, ["*", 2, 3]])
→ calculate(1) + calculate(["*", 2, 3])
→ 1 + calculate(["*", 2, 3])
→ 1 + (calculate(2) * calculate(3))
→ 1 + (2 * calculate(3))
→ 1 + (2 * 3)
→ 1 + 6
→ 7
これはコードの単純な評価です。しかし、未知の値を変数として式に投げ込むとどうなるでしょうか?
calculate(["+", Number(process.argv[2]), ["*", 2, 3]])
→ calculate(Number(process.argv[2])) + calculate(["*", 2, 3])
→ Number(process.argv[2]) + calculate(["*", 2, 3])
→ Number(process.argv[2]) + (calculate(2) * calculate(3))
→ Number(process.argv[2]) + (2 * calculate(3))
→ Number(process.argv[2]) + (2 * 3)
→ Number(process.argv[2]) + 6
ここで、明確な部分評価の違いを見ることができます。Number(process.argv[2]) を評価する方法がわかりません。その答えが何になるのか全くわかりません。しかし、このプロセスの過程で、それに関するいくらかの部分的な情報がわかっています。例えば、次のような場合です。
if (typeof expr === "number") return expr;
Number(process.argv[2]) が確かに数値であることを知っています。したがって、それをさらに部分的に評価できます。これがすべて理解できていることを願っています。しかし、もしあなたが私と同じなら、これらすべては少し些細で面白くないように思えるかもしれません。では、より複雑な例を見てみましょう。
function brainfuck(code, input = "") {
const tape = new Uint8Array(30000);
const jumps = {},
stack = [];
let pointer = 0,
inputPointer = 0,
output = "";
for (let i = 0; i < code.length; i++) {
if (code[i] === "[") stack.push(i);
if (code[i] === "]") {
const start = stack.pop();
jumps[start] = i;
jumps[i] = start;
}
}
for (let i = 0; i < code.length; i++) {
switch (code[i]) {
case ">":
pointer++;
break;
case "<":
pointer--;
break;
case "+":
tape[pointer]++;
break;
case "-":
tape[pointer]--;
break;
case ".":
output += String.fromCharCode(tape[pointer]);
break;
case ",":
tape[pointer] = inputPointer < input.length ? input.charCodeAt(inputPointer++) : 0;
break;
case "[":
if (!tape[pointer]) i = jumps[i];
break;
case "]":
if (tape[pointer]) i = jumps[i];
break;
}
}
return output;
}
brainfuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
ここではBrainfuckインタープリタがあります。そして、部分評価したい例のプログラムは、まったく入力(Brainfuckでは,が入力取得の方法です)を必要としません。そのため、部分評価を行うと、答えが得られます。この場合、このプログラムは実際にはBrainfuckの「hello world」です。しかし、入力のあるプログラムはどうでしょうか?
function main() {
return brainfuck(",>++[>+++[>++++[<<<+>>>-]<-]<-]<.", process.argv[2])
}
部分評価を行うと、次のようになります。
function main(b) {
let a;
a: {
a = process.argv[2];
a = a === void 0 ? "" : a;
if (0 < a.length) {
a = a.charCodeAt(0);
break a;
}
a = 0;
}
a = (a & 255) + 24 & 255;
return String.fromCharCode(a);
}
これは何でしょう?コンパイルされたBrainfuckプログラムです!これが最初の信じられない事実です。インタープリタを取り、それをプログラムで部分評価すると、コンパイルされたプログラムが得られるのです!この特定の正確な形式は、私の部分評価器の動作方法の成果です。わずかに異なるコードを想像できるかもしれません。しかし、重要なのは、インタープリタを完全に削除したということです。
プロジェクション
ここで発見したのは、いわゆる「Futamura Projection」の最初のものです。私たちの部分評価器は、インタープリタとプログラムを与えられたときに、プログラムのコンパイルされたバージョンを提供できます。疑似コードで表現すると、次のようになります。
partial_eval(interpreter, prog) -> compiled_prog
インタープリタやコンパイラに触れた経験によって、これは奇跡のように聞こえるか、ありふれたものに聞こえるかもしれません。インタープリタを書くこととコンパイラを書くことは、大きく異なる取り組みのように思えるかもしれません。AIの時代には、おそらくそうではないかもしれませんが、それでも多くのことが当てはまると私は思います。インタープリタを計装するのは非常に簡単ですが、コンパイラではそれほど簡単ではありません。インタープリタを変更して新しい機能に対応するのは非常に簡単ですが、コンパイラではそうではありません。しかしそれ以上に、インタープリタと見なせるものの、コンパイラを書こうとは決して思わないようなものが数多くあります。
function validate(schema, value) {
switch (schema.type) {
case "string":
return typeof value === "string" &&
(schema.minLength === undefined || value.length >= schema.minLength);
case "number":
return typeof value === "number" && Number.isFinite(value) &&
(schema.min === undefined || value >= schema.min);
case "boolean":
return typeof value === "boolean";
case "array":
if (!Array.isArray(value)) return false;
const length = value.length;
for (let i = 0; i < length; i++) {
if (i in value && !validate(schema.items, value[i])) return false;
}
return true;
case "object":
return value !== null && typeof value === "object" &&
!Array.isArray(value) &&
Object.keys(schema.properties).every(key =>
Object.hasOwn(value, key) &&
validate(schema.properties[key], value[key]));
default:
throw new Error("Unknown schema type: " + schema.type);
}
}
const userSchema = {
type: "object",
properties: {
name: { type: "string", minLength: 1 },
age: { type: "number", min: 0 },
tags: { type: "array", items: { type: "string" } }
}
};
function validateUser(value) {
return validate(userSchema, value);
}
この単純なスキーマ設定を考えてみてください。これは、特定のスキーマに対して特殊化された関数を作成した、部分評価可能なコードです。最も重要なコードではありませんが、オブジェクトがより複雑になり始めると、5倍のパフォーマンス向上が得られます。これらの関数を手書きすべきだと思うかもしれません。あるいは、これらのスキーマ用のコンパイラを手書きすべきだと。しかし、実行時にのみ存在するスキーマはどうでしょうか?ここで、実行時にコンパイルするか、コンパイラとインタープリタの両方を保持する必要があります。部分評価の方法があると、この負担がかなり軽減されます。
頭がクラクラするような話
しかし、Futamura Projectionがここで止まったら、それはエキサイティングではあるものの、クレイジーさには欠けるでしょう。これがさらに進む方法を理解するために、部分評価するということの生の直感から一歩進んで、異なるフレームワークを与えます。部分評価を「特殊化」のプロセスとして考えることができます。
プログラムの特殊化とは具体的に何でしょうか?それは、汎用的なプログラムを取り、単一のプログラムのために機能するバージョンを作成することです。単純なパターンマッチングプログラムを、非常に単純化された正規表現として考えてみましょう。
function matches(pattern, text) {
if (pattern.length === 0) {
return text.length === 0;
}
const firstCharacterMatches =
text.length > 0 && pattern[0] === text[0];
const allowsRepetition = pattern[1] === "*";
if (allowsRepetition) {
const remainingPattern = pattern.slice(2);
if (matches(remainingPattern, text)) {
return true;
}
if (!firstCharacterMatches) {
return false;
}
const remainingText = text.slice(1);
return matches(pattern, remainingText);
}
if (!firstCharacterMatches) {
return false;
}
const remainingPattern = pattern.slice(1);
const remainingText = text.slice(1);
return matches(remainingPattern, remainingText);
}
matches("a*b*c", "aaabbc");
このプログラムは汎用的です。さまざまなパターンにマッチさせることができます。柔軟性が必要な場合は、これは素晴らしいことです。しかし、多くのパターンがない場合は、特殊化されたコードを作成する価値があるかもしれません。では、具体的にどのような特殊化されたコードでしょうか?リテラルパターンしかない場合、非常に特別に特殊化したいと思うでしょう。
function matchesAStarBStarC(text) {
let i = 0;
while (text[i] === "a") i++;
while (text[i] === "b") i++;
return text[i] === "c" && i + 1 === text.length;
}
matchesAStarBStarC("aaabbc");
あるいは、単に<x>*<y>*<z>*のようなパターンです。
function matchesXStarYStarZStar(x, y, z, text) {
let i = 0;
while (i < text.length && text[i] === x) i++;
while (i < text.length && text[i] === y) i++;
while (i < text.length && text[i] === z) i++;
return i === text.length;
}
matchesXStarYStarZStar("a", "b", "c", "aaabbc");
汎用的なコードのどの部分についても、より特殊化された形式にコードを移動する方法を考えることができます。
スペシャライザーの特殊化
部分評価は特殊化の一形態であり、どの入力が静的でどの入力が動的かに基づいて何を特殊化するかを判断します。多くの点で、部分評価器は汎用スペシャライザーです。任意のプログラムを与えられれば、任意の入力に対して特殊化されたバージョンを作成できます。インタープリタを特定の入力に対して特殊化するとどうなるでしょうか?そのインタープリタは、そのプログラム専用になります。では、そのとき何が必要でしょうか?この汎用的なディスパッチのすべてが必要でしょうか?いいえ、完全なプログラムを知っています。実際には使用しない操作は必要ありません。汎用インタープリタメカニズム全体を完全に削除できます。
しかし、スペシャライザーが任意のプログラムを特殊化できるなら、それは自分自身を特殊化できるでしょうか?
これが2番目のFutamura Projectionにつながります。疑似コード形式で表現すると、次のようになります。
partial_eval(partial_eval, interpreter) -> compiler
あるいは、スペシャライザー言語で表現すると、汎用スペシャライザーの特殊バージョンを作成したらどうなるでしょうか?それは何のために特殊化されるのでしょうか?特定のインタープリタです。これで、任意のプログラムを与えると、そのプログラム専用の特殊化されたインタープリタを生成する関数が得られます。つまり、Java風に言えば、特殊化されたインタープリタファクトリを持っています。
このコンパイラの具体的な例を見て、これを具体的にしましょう。ここで、特殊化するインタープリタを示します。
function interp(program, io) {
var value = null;
while (program.length > 0) {
var instruction = program[0];
if (instruction === "prompt") {
value = io.prompt();
} else if (instruction === "print") {
io.print(value);
} else {
throw new Error("Unknown instruction: " + instruction);
}
program = program.slice(1);
}
return value;
}
2番目のProjectionを適用すると、次のコンパイラが得られます。
function compile(program) {
const lines = codegen.buffer();
const literalSource = codegen.literal(null).source;
let remaining = program;
let value = literalSource;
while (remaining.length > 0) {
const remainingItem = remaining[0];
if (remainingItem === "prompt") {
const ioReference = codegen.reference("io");
const callSource = codegen.call(lines, ioReference, "prompt", []).source;
remaining = remaining.slice(1);
value = callSource;
continue;
}
if (remainingItem === "print") {
const ioReference2 = codegen.reference("io");
const args = [codegen.reference(value)];
codegen.call(lines, ioReference2, "print", args);
remaining = remaining.slice(1);
continue;
}
const text = "Unknown instruction: " + remainingItem;
throw new Error(text);
}
const valueReference = codegen.reference(value);
return codegen.finish(lines, valueReference);
}
そして、これらの非常に単純なプログラムの1つをコンパイルすると、出力を見ることができます。
compile(["prompt", "print"])
// returns as a string
function run(io) {
var v0 = io.prompt();
var v1 = io.print(v0);
return v0;
}
もちろん、これはあまり興味深い言語ではありません。しかし、この一般的なアイデアが見えるはずです。インタープリタを与えると、コンパイラが自動的に導き出されます!非常に信じられないことです。
3番目のProjection
しかし、2番目のProjectionで止まることはできません。最終的な頭がクラクラするようなProjectionに到達するために、さらに進む必要があります。スペシャライザー自身を入力として適用すると、コンパイラジェネレーターが得られます。
partial_eval(partial_eval, partial_eval) -> compiler_generator
これで、任意のインタープリタを与えるとコンパイラを生成する汎用関数が得られました!
遊んでみる
私はRustでJavaScript用の、まともだがまだ非常に限定的な部分評価器を実装しました。さらに、JavaScriptの多くの異なるインタープリタやインタープリタライクなプログラムでうまく機能するように努めました。また、2番目と3番目のProjectionの限定的なバージョンを機能させることも試みました。ぜひ遊んでみて、何が機能し、何が機能しないかを確認し、問題を報告してください。あるいは、より多くのケースを機能させるために、トークンの一部を使って私を助けてください。
しかし何よりも、探求してください。これは非常に豊かな分野です。以下は、何らかの形で部分評価に関する論文、ブログ、プロジェクトのリストです。プログラミング言語のこれらの種類のクレイジーなテクニックを試すのに、これほど良い時期はありませんでした。実用的なものに、クールで興味深いプログラミングの側面を探求することを妨げさせないでください。
- weval: WebAssemblyの部分評価器
- JavaScriptからWasmへのコンパイル、パート3:部分評価 — Chris Fallin
- Futamura Projectionの第一歩 — Veit Heller
- Truffleの部分評価 — Graalドキュメント
- 計算プロセスの部分評価 — コンパイラコンパイラへのアプローチ — Yoshihiko Futamura (1971年、元の英訳)
- 部分評価と自動プログラム生成 — Neil D. Jones, Carsten K. Gomard, and Peter Sestoft
- オンライン部分評価チュートリアル — William R. Cook and Ralf Lämmel