部分求值的魔力

Lobsters Hottest 工具

摘要

Jimmy Miller 探索了部分求值的概念——在编译时展开程序以消除静态计算——这一想法源于 James Long 对 Meta 的 Prepack 的复兴,他还介绍了自己开发的用于试验这一想法的库。

<p><a href="https://lobste.rs/s/silxsl/magic_partial_evaluation">评论</a></p>
查看原文
查看缓存全文

缓存时间: 2026/11/19 03:08

# 部分求值的魔力 — Jimmy Miller 来源:https://jimmyhmiller.com/magic-of-partial-evaluation 软件领域中有些思想就是纯粹的美。它们是否实用无关紧要,你是否能说服同事去关注它们也无关紧要。某些计算系统运作的方式本身就有一种迷人的魅力。对我来说,最美的软件是那些能揭示编程语言本质的东西。编程语言是我的痴迷。我从未遇到过一个引入新编程语言解决不了的问题。在编程语言层面解决问题,本质上是解决元问题。我们不是去试图解决某个特定问题,而是退后一步,问如何一次性解决一整类问题。所以,当我发现某些东西让我重新思考编程语言的本质时,我就会开始重新思考整个计算。 这些极其美丽却又棘手的概念之一,叫做部分求值(partial evaluation)。如果你对解释器和编译器着迷,部分求值会告诉你它们之间的关系,以及你如何免费获得一个编译器。 ## 部分求值,简单模式 部分求值长期以来一直让我着迷。但整件事的起因是 James Long 宣布他复活了 [Meta 用于 JavaScript 的部分求值器 prepack](https://x.com/jlongster/status/2118465154354385010)。我第一次听说 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 投影中的第一个。我们的部分求值器,当应用于一个解释器并给定一个程序时,可以给我们该程序的编译版本。或者用伪代码表示: `partial_eval(interpreter, prog) -> compiled_prog` 根据你对解释器和编译器的了解程度,这可能看起来像奇迹,也可能平淡无奇。编写解释器和编写编译器看起来是截然不同的任务。在 AI 时代,也许不再那么明显,但我认为即使如此,许多事情仍然成立。给解释器加上插桩(instrumentation)是相当容易的,而给编译器做同样的事则难得多。修改解释器以支持新功能相当容易,编译器则不然。 但更重要的是,有各种各样的东西都可以被看作是解释器,而我们几乎永远不会为它们编写编译器。 ``` 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 呢?现在我们要么需要即时编译它们,要么必须同时维护一个编译器和一个解释器。拥有部分求值的能力大大减轻了这种负担。 ## 思维颠覆 但如果 Futamura 投影仅止于此,它们虽然令人兴奋,却还没有达到其真正的疯狂程度。为了理解这如何能更进一步,我们将超越你对部分求值的原始直觉,换一个框架来看。 我们可以把部分求值看作是"特化"(specializing)一个程序的过程。特化一个程序究竟是什么?就是把一个通用的程序,变成一个只适用于单一程序的版本。让我们想一个简单的模式匹配程序,比如一个过度简化的正则表达式。 ``` 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"); ``` 或者你只有 `***` 作为模式。 ``` 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 投影。用我们的伪代码格式表示: `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; } ``` 当我们应用第二个投影时,得到了下面这个编译器: ``` 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); } ``` 而如果我们编译一个……

相似文章

Haskell惰性求值不完全指南 (2015)

Lobsters Hottest

本文提供了关于Haskell中惰性求值的指南,解释了其机制、对模块化代码的好处,以及分析空间和时间使用的方法。

生成式编译:AI生成代码时的即时编译器反馈

Hugging Face Daily Papers

本文介绍了生成式编译,一种在AI生成代码过程中获取部分程序编译器反馈的方法,利用“sealor”变换使得标准编译器能够诊断不完整的代码。在Rust编码任务上的评估表明,该方法通过及早捕获错误,减少了无法编译的输出并提高了功能正确性。

法官代码化:通过程序蒸馏实现可扩展评估

arXiv cs.AI

本文介绍了PAJAMA,这是一个将大语言模型作为评判者的决策逻辑蒸馏到程序化评判者中的系统,消除了每次样本的API成本,同时匹配了13B大语言模型评判者的性能,并为可扩展评估提供了透明度和效率改进。