软件中有一些想法就是很美。它们是否有任何实际用途并不重要。你永远无法说服同事去考虑它们,这也不重要。某些计算系统的运作方式就是有某种令人着迷之处。
对我来说,最美的软件是那些揭示了编程语言本质某些东西的软件。编程语言是我的执念。我从未遇到过一个不能通过再引入一门编程语言来解决的问题。在编程语言层面解决问题,关乎解决元问题。与其试图解决某个特定问题,我们退后一步,问如何一次性解决一整类问题。
所以,当我发现某种让我重新思考编程语言本质的东西时,我就开始重新思考整个计算。这些极其美丽却又棘手的概念之一,名叫部分求值。如果你对解释器和编译器着迷,部分求值会教你这二者如何相关,以及如何免费得到一个编译器。
部分求值的简单模式
部分求值曾在一段时间里让我着迷。但整件事出现,是在 James Long 宣布他重新启用了 Meta 的、名为 prepack 的 JavaScript 部分求值器时。我第一次听说 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))))
我们在这两种情况中所做的,叫做部分求值。在第一种情况中,这是一个平凡情形,因为一切都是静态已知的。但在后一种情况中,我们把一个程序归约到其动态结构的本质。不再剩下递归函数调用。所有这些都被尽可能展开,直到只剩下代码的动态部分。
核心思想
这种直观的部分求值概念,就是欣赏这里之美所需要知道的全部。部分求值只是求值程序中我们能在构建时求值的那部分,并留下其余所有部分。当我们以某些组合对某些程序这样做时,会得到一些相当令人惊讶、不可思议的行为。
写成 {{NAME_ab12cd34}} 这样的值是真实值的占位符。请完全按照书写形式使用它们,在回复和工具调用中都一样:它们会在任何内容运行之前被填入真实值。不要要求验证它们,也不要用示例替换它们。
部分求值的魔力
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]) 确实是一个 number。所以我们可以进一步对它进行部分求值。希望这一切都说得通。但如果你像我一样,这一切可能看起来有点琐碎和无趣。所以让我们看一个更复杂的例子。
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);
}
文章标题:The Magic of Partial Evaluation
正文: 这是什么?一个编译后的 brainfuck 程序!这是第一个令人难以置信的事实:当你拿一个解释器,并用一个程序对它进行部分求值时,你就能得到编译后的程序!现在这个特定的确切形式是我的部分求值器工作方式所产生的产物。你可以想象略有不同的代码。但关键在于,我们所做的是完全移除了解释器。
The Projections
我们在这里发现的是三个所谓的 Futamura 投影中的第一个。我们的部分求值器,当应用于一个解释器并给定一个程序时,可以为我们提供该程序的编译版本。或者用伪代码来表示。
取决于你对解释器和编译器的接触程度,这可能看起来像是奇迹,也可能显得平淡无奇。编写解释器和编写编译器可能看起来像是截然不同的工作。在 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);
}
考虑这个简单的 schema 设置。这段代码很容易被部分求值成我们为特定 schema 创建了专用函数的形式。虽然这不是最关键的部分,但当我们的对象开始变得更复杂时,这可以给我们带来 5 倍的性能提升。你可能认为我们应该直接手写这些函数。或者手写一个针对这些 schema 的编译器。但那些只在运行时才存在的 schema 呢?现在我们要么需要即时编译它们,要么必须同时保留一个编译器和解释器。有一种部分求值的方法可以大大减轻这一负担。
Mind Bending
但如果 Futamura 投影止步于此,它们虽然令人兴奋,却还谈不上疯狂。为了理解这如何能更进一步,我们要超越你对部分求值含义的直觉,给出一个不同的框架。我们可以把部分求值看作一个“特化”程序的过程。
特化一个程序到底是什么?嗯,就是拿一个通用的程序,做成一个只适用于单个程序的版本。让我们想一个简单的模式匹配程序,比如一个过度简化的正则。
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("abc", "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");
对于任何一段通用代码,我们都可以思考如何把代码转成更专门化的形式。
## 特化特化器#
部分求值是一种特化形式,它根据哪些输入是静态的、哪些是动态的来决定应该特化什么。在许多方面,部分求值器就是一个通用特化器。给定任何程序,我们都能为任何输入生成它的特化版本。如果我们针对给定输入特化一个解释器,会发生什么?我们拿回来的就是只针对那一个程序的解释器。但那时我们需要什么?我们需要所有这些通用分派吗?不需要,我们知道完整程序。我们不需要任何实际用不到的操作。我们可以完全去掉所有通用解释器机制。
但如果特化器能特化任何程序,它能特化自身吗?
这引出了第二 Futamura 投影。用我们的伪代码格式来表示,我们得到:
或者,用我们的特化器语言来说,如果我们制作一个通用特化器的特殊版本会怎样?它特化用于什么?一个特定的解释器。现在我们有一个函数,给定任何程序,就会专门为该程序输出新特化的解释器。或者,用 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; }
当我们应用第二投影时,我们得到以下编译器:
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); }
如果我们编译其中一个非常简单的程序,就能看到输出:
compile(["prompt", "print"])
// returns as a string function run(io) { var v0 = io.prompt(); var v1 = io.print(v0); return v0; }
当然,现在这并不是一门非常有趣的语言。但希望你能看到这个总体思路。给定一个解释器,我们就能自动派生出一个编译器!相当不可思议。
## 第三次投影#
但我们不能停在第二次投影。我们必须继续推进,抵达最终那个颠覆认知的投影。如果你把我们的特化器作为输入喂给它自己,你得到的就是一个编译器生成器。
partial_eval(partial_eval, partial_eval) -> compiler_generator
所以现在我们有了一个通用函数,能为我们给它提供的任何解释器吐出编译器!
把玩它
我在 Rust 中为 JavaScript 实现了一个还算合理、但仍然非常有限的部分求值器。我把它推得更远,试图让它能相当好地适用于若干不同的解释器以及类解释器的 JavaScript 程序。我还尝试让第二、第三次投影的受限版本跑起来。去把玩一下它吧,看看哪些能用、哪些不能用,提交 issue,或者更好的是,用你的一些 token 帮我让更多 case 跑通。
但最重要的是,去探索。这是一个如此丰富的空间。下面是一些以某种方式、形态或形式涉及部分求值的论文、博客和项目。现在正是把玩这类疯狂编程语言技术的最好时机。别让「实用」阻止你去探索编程中那些酷而有趣的方面。
- weval:WebAssembly 部分求值器
- 把 JavaScript 编译到 Wasm,第 3 部分:部分求值 — Chris Fallin
- 第一次 Futamura 投影 — Veit Heller
- Truffle 中的部分求值 — Graal 文档
- 计算过程的部分求值——一种编译器-编译器的方法 — Yoshihiko Futamura(1971,最初的英文译本)
- 部分求值与自动程序生成 — Neil D. Jones、Carsten K. Gomard 和 Peter Sestoft
- 在线部分求值教程 — William R. Cook 和 Ralf Lämmel