Partial evaluation in guile › 钻进兔子洞 _{down the rabbit hole} [#272]

March 16, 2025
Andy Wingo

到这里一切都还很简单：我们有一个终止 ( terminates ) 的简单、良类型 ( well-typed ) 的例子。但要成为真实世界的编译器的一部分，一个部分求值器需要能够应对真实世界的代码：可变数据的访问器，访问可变绑定（词法和全局的），可能无限的递归，未绑定变量，以及贫瘠类型 ( poorly-typed ) 的程序。此外，一个真实世界的内联器还需要运行得快，并避免产生膨胀的留存代码。

Up to here things are easy: we have a simple, well-typed example that terminates. But to be part of a real-world compiler, a partial evaluator needs to handle real-world code: accessors for mutable data, access to mutable bindings (lexical and global), indefinite recursion, unbound variables, and poorly-typed programs. In addition, a real-world inliner needs to run quickly and avoid producing bloated residual code.

我应该花点时间指出，静态类型的函数式语言只要简单定义一下，就能避免许多这些问题。编译器专家们倾向于使用早期绑定就不奇怪了。Scheme 确实通过对词法作用域的使用展现了一定程度的早期绑定，但它并不是一个纯函数式语言。在开发 peval 时，是我第一次希望 Scheme 中有不可变的对 ( pairs ) ，就像 Racket 和 R6RS 推广的那样。

I should take a moment and note that statically-typed, functional languages can avoid a number of these problems, simply by defining them away. It is no wonder that compiler people tend towards early binding. Scheme does exhibit a fair amount of early binding through its use of lexical scope, but it is not a pure functional language. Working on this peval was the first time that I wished for immutable pairs in Scheme, as promoted by Racket and R6RS.

无论如何，在你的语言中拥有可变性并不是那么的糟糕。你确实错过了一些优化机会，但这没关系。更糟的是生产环境中 peval 在一个表达式花费太多时间。

Anyway, having mutability in your language isn't so bad. You do miss some optimization opportunities, but that is OK. What is not OK in a production peval is spending too much time on an expression.

Guile 的解决方案，遵循 Waddell 和 Dybvig 卓越的 Fast and Effective Procedure Inlining 中的方法，只需计算通过内联器的次数。每次内联尝试都会得到一个新的计数器，在内联尝试中的任何工作都会减少计数器的值。当计数器归零时，内联尝试被中止，取而代之的是留存一个调用。由于程序中的调用点 ( call sites ) 数量是固定的，且每个调用点将完成的工作量是有限的，因此最终的算法在源程序大小为 N 时是 O(N)。

Guile's solution, following Waddell and Dybvig's excellent Fast and Effective Procedure Inlining, is to simply count the number of times through the inliner. Each inlining attempt gets a fresh counter, and any work performed within an inlining attempt decrements the counter. When the counter reaches zero, the inlining attempt is aborted, and a call is residualized instead. Since the number of call sites in the program is fixed, and there is a maximum amount of work that will be done at each call site, the resulting algorithm is O(N) in the size of the source program.

为了让定义在他们被使用的上下文中被处理，Guile 的部分求值器还使用了 Waddell 和 Dybvig 的按需 ( on-demand ) 、在线 ( online ) 策略。例如，当 (cons 1 2) 被作为条件测试处理时，可能会被化简为 #t。如果在处理 let 的 body 后，一个绑定没有被引用，那么他会被作为效应 ( effect ) 处理。诸如此类。

Guile's partial evaluator also uses the on-demand, online strategy of Waddell and Dybvig, to allow definitions to be processed in their use contexts. For example, (cons 1 2) may be reduced to #t when processed as a test, in a conditional. If, after processing the body of a let, a binding is unreferenced, then it is processed for effect. Et cetera.

工作量 ( effort ) 计数器设置后，Guile 只是简单地尝试内联程序中的每一个调用点，因为如果不奏效它自己会退出。这听起来有些疯狂，但正如 Waddell 和 Dybvig 展示的，这是有效的。工作量计数器也用于限制代码增长，尽管这方法有些粗糙。无论如何，当我优化 Guile 使用的 psyntax 扩展器时，代码的增长量不到百分之一，这对我来说是个胜利。

With the effort counter in place, Guile simply tries to inline every call site in the program, knowing that it will bail out if things don't work. It sounds a little crazy, but it works, as Waddell and Dybvig show. The effort counter also serves to limit code growth, though it is a bit crude. In any case I got less than a percent of code growth when optimizing the psyntax expander that Guile uses, which is a win in my book.

Context

Translation. Partial evaluation in guile [jsr-0015]

March 16, 2025
Andy Wingo with contributions from Jinser Kafka
Original

tips: Click on the translation to expand and view the original text. 点击译文可展开查看原文。

Translated according to the version last updated on 11 October 2011 10:01 AM.

根据2011年10月11日上午10:01更新的版本翻译。

朋友们，就在刚刚发生了一件很棒的事情：Guile 获得了一个值得尊敬的内联器 ( inliner ) 。

Friends, something awesome just happened: Guile just got itself a respectable inliner.

我以前在这个博客说过，引用评论者 Rémi Forax 的话说，“内联是所有优化之母”。的确如此，内联为代码移动，常量折叠，死代码消除，循环优化开辟了空间。然而，功劳可能更应该归功于部分求值 ( partial evaluation ) ，这位所有内联优化之母。

I have said before on this blog, quoting commenter Rémi Forax, that "inlining is the mother of all optimizations". It is true that inlining opens up space for code motion, constant folding, dead code elimination, and loop optimizations. However, credit might be better laid at the feet of partial evaluation, the mother of all inlining algorithms.

部分求值是一种源到源的转换，它接收你的程序并产生一个更好的程序：其中任何可以在编译时完成的计算都已完成，只留下那些需要在运行时进行的计算。

Partial evaluation is a source-to-source transformation that takes your program and produces a better one: one in which any computation that can be done at compile-time is already made, leaving only those computations that need to happen at run-time.

例如，这个应用

For example, the application

(+ 2 3)

可以明确地在编译时求值。我们说源表达式 (+ 2 3) 通过常数折叠简化为 5，得到的结果（在这个情况下是 5）是留存 ( residual ) 表达式。

can clearly be evaluated at compile-time. We say that the source expression (+ 2 3) reduces to 5 via constant folding. The result, 5 in this case, is the residual expression.

一个更复杂的例子：

A more complicated example would look like:

(let ((string->chars
       (lambda (s)
         (define char-at
           (lambda (n) (string-ref s n)))
         (define len
           (lambda () (string-length s)))
         (let loop ((i 0))
           (if (< i (len))
               (cons (char-at i)
                     (loop (1+ i)))
               '())))))
  (string->chars "yo"))
=> (list #\y #\o)

当我在这里写下 =>，你应该将它读作“ 在编译时留存 ( residualizes at compile-time to ) ”。在这里，我们的输入程序在编译时留存为一个简单的 list 构造。循环完全被展开 ( unrolled ) ，字符串引用折叠，所有叶子过程 ( leaf procedures ) 都被内联。

Here when I write =>, you should read it as, "residualizes at compile-time to". In this case our input program residualized, at compile-time, to a simple list construction. The loop was totally unrolled, the string-refs folded, and all leaf procedures were inlined.

很棒吧？

Neat, eh?

优化解锁表达能力 _{optimization enables expressiveness} [#270]

March 16, 2025
Andy Wingo

如果部分求值器好好完成他的任务，那么留存程序会运行得更快。然而我对此如此满意的真正原因不是这个；而是它能够让我编写不同的程序。

If the partial evaluator does its job right, the residual program will run faster. However this isn't the real reason that I'm so pleased with it; rather, it's that it lets me write different programs.

你知道，我一直在研究 Guile 编译器和虚拟机。当我写代码时，我知道 Guile 会如何处理这些代码。不幸的是，这导致我的程序要比必要的代码丑，因为我知道 Guile 不会为我内联一些重要的东西。我在比较底层的抽象写代码，因为我不信任编译器。

You see, I hack on Guile's compiler and VM and all that. When I write code, I know what Guile is going to do with it. Unfortunately, this caused my programs to be uglier than necessary, because I knew that Guile wasn't going to inline some important things for me. I wrote at a lower level of abstraction, because I couldn't trust the compiler.

现在，有了部分求值器，我很乐意使用辅助函数，甚至高阶的辅助函数，因为 Guile 基本上会做正确的事。这在支持语法抽象的语言中格外重要，比如 Scheme。如果你是一名 Schemer，但还没有看过 Kent Dybvig 的 Macro Writers' Bill of Rights 演讲（幻灯片），请务必看看。

Now, with the partial evaluator, I'm happy to use helper functions, even higher-order helpers, with the knowledge that Guile will mostly do the right thing. This is particularly important in the context of languages that support syntactic abstraction, like Scheme. If you're a Schemer and haven't seen Kent Dybvig's Macro Writers' Bill of Rights talk (slides), do check it out.

顺便一提，几周前，JSConf.eu 上发生了一件悲伤的事，Andreas Gal（即使是他！）为了获得足够的速度，他不得不手动内联 PDF.js 中的一些函数。不过，稍后再详细介绍 JavaScript。

Incidentally, there was a sad moment in JSConf.eu a couple weekends ago when Andreas Gal (of all people!) indicated that he had to manually inline some functions in PDF.js in order to get adequate speed. More on JavaScript a little later, though.

关于部分求值 _{about partial evaluation} [#271]

March 16, 2025
Andy Wingo

部分求值看起来很像一个常规的自循环解释器 ( meta-circular evaluator ) 。这是一个递归函数，接受一个表达式和一个环境 ( environment ) ，返回一个值。Guile 的部分求值器 peval 会在看到 let 和其他绑定构造 ( binding constructs ) 时建立词法 ( lexical ) 环境，并在看到词法引用时尝试传播 ( propagate ) 拷贝。

A partial evaluator looks a lot like a regular meta-circular evaluator. It's a recursive function that takes an expression and an environment and yields a value. Guile's partial evaluator, peval, builds up lexical environments when it sees let and other binding constructs, and tries to propagate copies when it sees lexical references.

内联是通过 lambda 表达式的拷贝传播 ( copy-propagation ) 实现的。正如上例中初始值 0 通过词法变量 i 传播到 (< i (len)) 一样，(lambda () (string-length s)) 传播到 len。lambda 表达式的应用可简化到与 let 绑定等价。因此，对于上面的 loop 的第一次迭代，我们有：

Inlining is facilitated by copy-propagation of lambda expressions. Just as the initial value 0 in the example above propagates through the lexical variable i to reach (< i (len)), (lambda () (string-length s)) propagates to len. Application of a lambda expression reduces to the equivalent of a let binding. So for the first iteration of loop above, we have:

(< i (len))
;; copy propagation
=> (< 0 ((lambda () (string-length s))))
;; beta-reduction
=> (< 0 (string-length s))
;; copy-propagation
=> (< 0 (string-length "yo"))
;; constant-folding
=> (< 0 2)
;; constant-folding
=> #t

这里的条件直接被折叠成了一个常数。因此我们在编译时知道要执行哪一个分支。第二个分支已经死了，所以我们会消除它。这个过程一直持续到我们最终产生结果列表为止。

In this case the condition folded to a constant, so we know at compile-time which branch to take. The second branch is dead, so we eliminate it. The process continues until we finally produce the resulting list.

钻进兔子洞 _{down the rabbit hole} [#272]

March 16, 2025
Andy Wingo

Up to here things are easy: we have a simple, well-typed example that terminates. But to be part of a real-world compiler, a partial evaluator needs to handle real-world code: accessors for mutable data, access to mutable bindings (lexical and global), indefinite recursion, unbound variables, and poorly-typed programs. In addition, a real-world inliner needs to run quickly and avoid producing bloated residual code.

I should take a moment and note that statically-typed, functional languages can avoid a number of these problems, simply by defining them away. It is no wonder that compiler people tend towards early binding. Scheme does exhibit a fair amount of early binding through its use of lexical scope, but it is not a pure functional language. Working on this peval was the first time that I wished for immutable pairs in Scheme, as promoted by Racket and R6RS.

Anyway, having mutability in your language isn't so bad. You do miss some optimization opportunities, but that is OK. What is not OK in a production peval is spending too much time on an expression.

Guile's solution, following Waddell and Dybvig's excellent Fast and Effective Procedure Inlining, is to simply count the number of times through the inliner. Each inlining attempt gets a fresh counter, and any work performed within an inlining attempt decrements the counter. When the counter reaches zero, the inlining attempt is aborted, and a call is residualized instead. Since the number of call sites in the program is fixed, and there is a maximum amount of work that will be done at each call site, the resulting algorithm is O(N) in the size of the source program.

Guile's partial evaluator also uses the on-demand, online strategy of Waddell and Dybvig, to allow definitions to be processed in their use contexts. For example, (cons 1 2) may be reduced to #t when processed as a test, in a conditional. If, after processing the body of a let, a binding is unreferenced, then it is processed for effect. Et cetera.

With the effort counter in place, Guile simply tries to inline every call site in the program, knowing that it will bail out if things don't work. It sounds a little crazy, but it works, as Waddell and Dybvig show. The effort counter also serves to limit code growth, though it is a bit crude. In any case I got less than a percent of code growth when optimizing the psyntax expander that Guile uses, which is a win in my book.

警告 _caveats [#273]

March 16, 2025
Andy Wingo

部分求值只能传播定义是已知的绑定。在 Guile 中，这将内联限制于词法引用和原语 ( primitive ) 引用，并明确地排除了全局引用、模块导入或可变对象的字段。因此我们还没有跨模块的内联，除了那些滥用宏展开器的黑客技巧外。

Partial evaluation can only propagate bindings whose definitions are known. In the case of Guile, then, that restricts inlining to lexical references and primitive references, and notably excludes global references and module imports, or fields of mutable objects. So this does not yet give us cross-module inlining, beyond the hacks that abuse the macro expander.

这个观察有一个推论，即某些语言提倡一种难以分析的编程风格。我这里实际是在讨论面向对象的语言，特别是动态的面向对象语言。当你在 Java 中看到 o.foo()，至少有可能 foo 是一个 final 方法，所以你知道如果你选择这么做，你可以内联它。但在 JavaScript 中，如果你看到 o.foo()，你不知道任何信息：在运行时，o 的属性集可以，而且确实会变化，因为人们会对对象 o、它的原型，或 Object.prototype 做猴子补丁 ( monkey-patch ) 。在大多数 JS 实现中，你甚至可以改变 o.__proto__。即使你能看到你的 o.foo() 调用是由 o.foo = ... 赋值的，在 ES5 中你仍然不知道任何信息，因为 o 可能有一个 foo 属性的 setter。

This observation has a correlary, in that some languages promote a style of programming that is difficult to analyze. I'm really talking about object-oriented languages here, and the dynamic ones in particular. When you see o.foo() in Java, there is at least the possibility that foo is a final method, so you know you can inline it if you choose to. But in JavaScript if you see o.foo(), you don't know anything: the set of properties of o can and does vary at runtime as people monkey-patch the object o, its prototype, or Object.prototype. You can even change o.__proto__ in most JS implementations. Even if you can see that your o.foo() call is dominated by a o.foo = ... assignment, you still don't know anything in ES5, as o could have a setter for the foo property.

有几件事在 JavaScript 世界中减轻了这种不利情况。

This situation is mitigated in the JavaScript world by a couple of things.

首先，你不必以这种方式编程：你可以以一种更函数式的风格使用词法作用域。加上严格模式 ( string mode ) ，这让编译器可以看到对 foo 的调用可以被内联，只要 foo 在源程序中不是可变的。这是一个可以通过静态分析轻松证明的属性。

First of all, you don't have to program this way: you can use lexical scoping in a more functional style. Coupled with strict mode, this allows a compiler to see that a call to foo can be inlined, as long as foo isn't mutated in the source program. That is a property that is cheap to prove statically.

然而，如 Andreas Gal 发现的那样，这不是主流 JS 实现做的事。这真的是一种遗憾，对我们所写的程序产生了持久的影响。

However, as Andreas Gal found out, this isn't something that the mainstream JS implementations do. It is really a shame, and it has a lasting impact on the programs we write.

我甚至听到一些人说，在 JavaScript 中你应该避免深层词法绑定，因为访问时间取决于绑定的深度。虽然这对于当前的实现是对的，但这是实现的属性，而不是语言本身的属性。在严格模式中，不使用 with 和 eval 引入的绑定，这样可以快速计算每个函数表达式的自由变量集。当闭包 ( closure ) 被创建时，JS 的实现可以不使用某种嵌套作用域的句柄 ( handle ) ，而是直接复制自由变量的值，并将它们存储在与函数代码相关联的向量 ( vector ) 中（你看，闭包是包含数据的代码）。接着对这些变量的任何访问都通过向量而不是作用域对象进行。

I even heard a couple people say that in JS, you should avoid deep lexical bindings, because the access time depends on the binding depth. While this is true for current implementations, it is a property of the implementations and not of the language. Absent with and eval-introduced bindings, a property that is true in strict-mode code, it is possible to quickly compute the set of free variables for every function expression. When the closure is made, instead of grabbing a handle on some sort of nested scope object, a JS implementation can just copy the values of the free variables, and store them in a vector associated with the function code. (You see, a closure is code with data.) Then any accesses to those variables go through the vector instead of the scope.

对于被赋值的变量⸺再强调一次，这是一个可以静态证明的属性⸺你把变量放到一个新的“盒子”中，并重写对这些变量的访问，使其通过这个盒子进行。捕获一个自由变量时复制的是那个盒子，而不是它的值。

For assigned variables -- again, a property that can be proven statically -- you put the variables in a fresh "box", and rewrite accesses to those variables to go through that box. Capturing a free variable copies the box instead of its value.

这个技术没有什么新东西；Cardelli 和 Dybvig（也可能是其他人）在 80 年代各自独立发现。

There is nothing new about this technique; Cardelli and Dybvig (and probably others) discovered it independently in the 80s.

关于闭包实现的这一点与部分求值有关：人们不会太抱怨 JS 中糟糕的静态内联器，因为普遍差劲的闭包实现损害了词法抽象。真是遗憾！

This point about closure implementation is related to partial evaluation: people don't complain much about the poor static inliners of JS, because the generally poor closure implementations penalize lexical abstraction. Truly a shame!

我似乎离题了，不好意思！

It seems I have digressed. Sorry about that!

我谈到了闭包和词法作用域，这是可以实现静态内联的 JS 语言属性。JavaScript 实现支持内联的第二种（同时更重要的）方式是动态内联。几个月前我用这个问题钓鱼 ( trolled ) 。当动态内联工作时，它非常棒，尽管有一些条件限制了启发式方式（向下滚动到“inlining”，注意在这几个月中具体的启发式集合已经变化了。）。

I spoke about closures and lexical scope, properties of the JS language that can enable static inlining. The second (and more important) way that JS implementations can support inlining is dynamically. I trolled about that some months ago. Dynamic inlining is fantastic, when it works, though there are limiting heuristics (scroll down to "inlining", and note that the exact set of heuristics have changed in the intervening months).

所以我的最后一点是关于 Guile 表现出色，而 JS 实现表现不佳的事，出于公平起见，我们现在谈一个相反的点。我希望能够实现动态内联，但这意味着要将中间表示与 scheme 函数关联起来。由于 Guile 能够提前编译 ( ahead-of-time ) 代码，这意味着我们将不得不将中间表示序列化到磁盘上，就像 GCC 的新链接时优化器 ( link-time optimizer ) （LTO）做的那样。但我希望这个实现推迟到之后我们将编译后 Guile 的格式更改为 ELF，否则我们会有运行时内存大小膨胀的风险。

So my last point was about something that Guile does well that JS implementations do poorly, and it's fair that this point should be the reverse. I would like to be able to dynamically inline, but this would mean associating the intermediate representation with Scheme functions. As Guile can compile code ahead-of-time, this means we would have to serialize the IR out to disk, in much the same way as GCC's new link-time optimizer (LTO) does. But I would like to put that off until we change the format of compiled Guile code to be ELF. Otherwise we run the risk of bloating our runtime memory size.

尝试一下 _{try it out} [#274]

March 16, 2025
Andy Wingo

Guile 的部分求值器是我和我的 Guile 维护者同事 Ludovic Courtès 共同完成的工作，它的灵感来源于 William Cook 在 2011 年 DSL 会议上的演讲以及 Waddell 和 Dybvig 共同完成的 Fast and Effective Procedure Inlining.

Guile's partial evaluator was joint work between myself and my fellow Guile maintainer Ludovic Courtès, and was inspired by a presentation by William Cook at DSL 2011, along with the Waddell and Dybvig's Fast and Effective Procedure Inlining.

此代码当前仅在从 git 构建的 Guile 开发树中。如果没问题，它将成为 Guile 2.0.3 的一部分，应该会在几周内发布。

This code is currently only in the development Guile tree, built from git. Barring problems, it will be part of Guile 2.0.3, which should be out in a couple weeks.

你可以在命令提示符下查看优化器做了什么：

You can check out what the optimizer does at the command prompt:

>,optimize (let ((x 13)) (* x x))
$1 = 169
>,optimize (let ((x 13)) (* x foo))
$2 = (* 13 foo)

玩得开心，然后将 bug 发送到 [email protected]。

Have fun, and send bugs to [email protected].