Person. Andy Wingo [wingo]

https://wingolog.org/

Backlinks

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

到这里一切都还很简单：我们有一个终止 ( 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.

警告 _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].

Translation. Guile's reader, in guile [jsr-000R]

December 22, 2024
Andy Wingo with contributions from Jinser Kafka
Original

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

晚上好！今天的简短（大概？）记录是一些关于 guile 书呆子 ( nargery ) 的内容。

Good evening! A brief note today about some Guile nargery.

历史的弧线 _{the arc of history} [#278]

December 22, 2024
Andy Wingo

就像在你打开收音机并期望听到威豹乐队 ( Def Leppard ) 时开始出现的许多语言实现一样，Guile 也有下半部分和上半部分。下半部分是用 C 编写的，暴露了一个共享库和一个可执行文件，而上半部分是用语言本身（在 Guile 的情况下是“Scheme”）编写的，并在语言实现开始时由 C 代码以某种方式加载。

Like many language implementations that started life when you could turn on the radio and expect to hear Def Leppard, Guile has a bottom half and a top half. The bottom half is written in C and exposes a shared library and an executable, and the top half is written in the language itself (Scheme, in the case of Guile) and somehow loaded by the C code when the language implementation starts.

自2010年左右以来，我们一直在努力将用C语言编写的部分改用 Scheme 编写。上周的信件讨论了动态链接的实现的替换，从使用libltdl库替换为在低级dlopen包装器之上的 Scheme 实现。我以前写过关于在 Scheme 中重写 eval 的内容，更近期则谈到在 Scheme 中实现与 C 语言实现相同性能的道路有时是漫长的。

Since 2010 or so we have been working at replacing bits written in C with bits written in Scheme. Last week's missive was about replacing the implementation of dynamic-link from using the libltdl library to using Scheme on top of a low-level dlopen wrapper. I've written about rewriting eval in Scheme, and more recently about how the road to getting the performance of C implementations in Scheme has been sometimes long.

这些重写有堂吉诃德式 ( quixotic ) 的一面。我内心深处有一些关于正确与错误的感觉，并且我从根本上知道从 C 转向 Scheme 是正确的事情。很多时候这种感觉都是完全不理性的，在许多情况下也显得不合时宜⸺比如，如果你有一项需要为客户完成的任务，你需要坐下来思考从这里到目标的最小步骤，而直觉对于你如何到达那里并没有多大作用。但有一个项目可以让你按照自己喜欢的方式做某件事是美好的，即使这需要 10 年，那也没关系。

These rewrites have a quixotic aspect to them. I feel something in my gut about rightness and wrongness and I know at a base level that moving from C to Scheme is the right thing. Much of it is completely irrational and can be out of place in a lot of contexts -- like if you have a task to get done for a customer, you need to sit and think about minimal steps from here to the goal and the gut doesn't have much of a role to play in how you get there. But it's nice to have a project where you can do a thing in the way you'd like, and if it takes 10 years, that's fine.

不过除了难以言表的动机之外，用 Scheme 重写一些东西还是有具体的好处的。我发现 Scheme 代码更容易维护，嗯，而且相比 C 的常见陷阱 ( pitfall ) ，Scheme 显然更安全。如果有一天我重写 Guile 的垃圾收集器，这会减少我的工作量。而且，Scheme 代码还具有 C 语言所没有的功能：尾部调用 ( tail call ) 、可恢复的分隔延续 ( resumable continuations ) 、运行时检测 ( run-time instrumentation ) 等等。

But besides the ineffable motivations, there are concrete advantages to rewriting something in Scheme. I find Scheme code to be more maintainable, yes, and more secure relative to the common pitfalls of C, obviously. It decreases the amount of work I will have when one day I rewrite Guile's garbage collector. But also, Scheme code gets things that C can't have: tail calls, resumable delimited continuations, run-time instrumentation, and so on.

以定界延续 ( delimited continuations ) 为例，大约五年前，我为 Guile 编写了一个以并行并发 ML 为模型的轻量级并发设施。它允许数百万条 fibers 存在于系统上。当一个 fiber 需要阻塞 I/O 操作（读或写）时，它会暂停其延续，并在操作变得可能时安排重启它。

Taking delimited continuations as an example, five years ago or so I wrote a lightweight concurrency facility for Guile, modelled on Parallel Concurrent ML. It lets millions of fibers to exist on a system. When a fiber would need to block on an I/O operation (read or write), instead it suspends its continuation, and arranges to restart it when the operation becomes possible.

为了让这一切成真，Guile 必须做出很多改变。首先是定界延续本身。后来是 Scheme 中 ports 设施上半部分的完全重写，以允许 port 操作挂起和恢复。可恢复 fibers 的许多障碍已被消除，但 Fibers 手册仍然列出了相当多的障碍。

A lot had to change in Guile for this to become a reality. Firstly, delimited continuations themselves. Later, a complete rewrite of the top half of the ports facility in Scheme, to allow port operations to suspend and resume. Many of the barriers to resumable fibers were removed, but the Fibers manual still names quite a few.

Scheme read, in Scheme [#279]

December 22, 2024
Andy Wingo

这给带来了我们今天的记录：我刚刚在 Scheme 中也重写了 Guile 的 reader！reader 是获取字符流并将其解析为 S 表达式的部分。以前是C语言，现在是 Scheme。

Which brings us to today's note: I just rewrote Guile's reader in Scheme too! The reader is the bit that takes a stream of characters and parses it into S-expressions. It was in C, and now is in Scheme.

这样做的主要动机之一是希望使 read 可挂起。通过此更改，现在可以在 fibers 上实现 REPL（读取-评估-打印循环）。

One of the primary motivators for this was to allow read to be suspendable. With this change, read-eval-print loops are now implementable on fibers.

另一个动机是最终修复 Guile 无法记录某些数据源位置的 bug。Guile 过去会使用弱键 ( weak-key ) 哈希表来使从 read 返回的数据与源位置相关联。但这仅适用于 fresh value，不适用于小整数或字符等立即数，也不适用于 keyword 和 symbol 等全局唯一的非立即数。因此对于这些，我们就没有任何源位置。

Another motivation was to finally fix a bug in which Guile couldn't record source locations for some kinds of datums. It used to be that Guile would use a weak-key hash table to associate datums returned from read with source locations. But this only works for fresh values, not for immediate values like small integers or characters, nor does it work for globally unique non-immediates like keywords and symbols. So for these, we just wouldn't have any source locations.

该问题的一个可靠解决方案是返回带注解 ( annotation ) 的对象，而不是使用另外的表。由于 Scheme 的宏扩展器已经被设置为与带注解的对象（语法对象）一起使用，因此一个新的 read-syntax 接口会非常好用。

A robust solution to that problem is to return annotated objects rather than using a side table. Since Scheme's macro expander is already set to work with annotated objects (syntax objects), a new read-syntax interface would do us a treat.

在 C 语言中实现 read 很难做到。但在 Scheme 中实现 read 则毫无问题。不过，调整扩展器以期望在语法对象内包含源位置有些繁琐，且源位置信息的增加使得输出文件的大小增大了几个百分比⸺这在部分上是 .debug_lines DWARF 数据的增加带来的，但也和宏中语法对象的序列化源位置有关。

With read in C, this was hard to do. But with read in Scheme, it was no problem to implement. Adapting the expander to expect source locations inside syntax objects was a bit fiddly, though, and the resulting increase in source location information makes the output files bigger by a few percent -- due somewhat to the increased size of the .debug_lines DWARF data, but also due to serialized source locations for syntax objects in macros.

速度方面，目前切换到 Scheme 的 read 是一个退步 ( regression ) 。旧的 reader 在这台笔记本电脑上记录源位置时每秒大概可以解析 15 或 16 MB，或者关闭源位置，那么有 22 或 23 MB/s。新的 reader 在旧模式下，使用弱键侧表记录源位置的解析速度大概为 10.5 MB/s，关闭位置时为 13.5 MB/s。新的 read-syntax 速度大约是 12 MB/s。我们将在未来几个月继续优化这些性能，但与原来的 reader 编写时的情况不同的是，现在的 reader 主要在编译时使用。（它在读取 s 表达式作为数据时仍然有用，因此仍然有理由提升其速度。）

Speed-wise, switching to read in Scheme is a regression, currently. The old reader could parse around 15 or 16 megabytes per second when recording source locations on this laptop, or around 22 or 23 MB/s with source locations off. The new one parses more like 10.5 MB/s, or 13.5 MB/s with positions off, when in the old mode where it uses a weak-key side table to record source locations. The new read-syntax runs at around 12 MB/s. We'll be noodling at these in the coming months, but unlike when the original reader was written, at least now the reader is mainly used only at compile time. (It still has a role when reading s-expressions as data, so there is still a reason to make it fast.)

与 eval 的情况一样，在加载 Scheme 版本之前，我们仍然有一个 C 版本的 reader 可用于引导目的。这次重写令人高兴的是，我能够从 C reader 中删除与非默认词法语法相关的所有缺陷，很好地简化了未来的维护。

As is the case with eval, we still have a C version of the reader available for bootstrapping purposes, before the Scheme version is loaded. Happily, with this rewrite I was able to remove all of the cruft from the C reader related to non-default lexical syntax, which simplifies maintenance going forward.

尝试逐个 bug ( bug-for-bug ) 重写的一个有趣方面是你会发现 bug 和意外行为。比如，事实证明，从出现以来，Guile 总是不需要终止分隔符地 read #t 和 #f，因此 read "(#t1)" 将得到列表 (#t 1)。很奇怪，对吧？更奇怪的是，当 #true 和 #false 别名被添加到语言中，Guile 决定默认支持它们，但以一种奇怪的向后兼容的方式…所以 "(#false1)" 读作 (#f 1) 但 "(#falsa1)" 读作 (#f alsa1)。诸如此类的事还有不少。

An interesting aspect of attempting to make a bug-for-bug rewrite is that you find bugs and unexpected behavior. For example, it turns out that since the dawn of time, Guile always read #t and #f without requiring a terminating delimiter, so reading "(#t1)" would result in the list (#t 1). Weird, right? Weirder still, when the #true and #false aliases were added to the language, Guile decided to support them by default, but in an oddly backwards-compatible way... so "(#false1)" reads as (#f 1) but "(#falsa1)" reads as (#f alsa1). Quite a few more things like that.

总的来说，这次重写似乎是成功的，没有引入新的行为，甚至产生了相同的错误。然而，对于回溯 ( backtrace ) 而言，情况并非如此，因为回溯可以暴露出 read 函数的内部实现，而之前由于 C 栈对 Scheme 是不透明的，这种情况并不会发生。因此，我们可能需要在调用 read 的地方添加更合理的错误处理，因为回溯信息无论如何都不是一个好的面向用户的错误反馈。

All in all it would seem to be a successful rewrite, introducing no new behavior, even producing the same errors. However, this is not the case for backtraces, which can expose the guts of read in cases where that previously wouldn't happen because the C stack was opaque to Scheme. Probably we will simply need to add more sensible error handling around callers to read, as a backtrace isn't a good user-facing error anyway.

好吧，今晚的闲聊已经够多了。祝大家 happy hacking，晚安！

OK enough rambling for this evening. Happy hacking to all and to all a good night!

Contributions

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.

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)

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.

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.

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.

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

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.

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

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.

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.

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.

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!

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).

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'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].

Translation. Guile's reader, in guile [jsr-000R]

December 22, 2024
Andy Wingo with contributions from Jinser Kafka
Original

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

晚上好！今天的简短（大概？）记录是一些关于 guile 书呆子 ( nargery ) 的内容。

Good evening! A brief note today about some Guile nargery.

历史的弧线 _{the arc of history} [#278]

December 22, 2024
Andy Wingo

Like many language implementations that started life when you could turn on the radio and expect to hear Def Leppard, Guile has a bottom half and a top half. The bottom half is written in C and exposes a shared library and an executable, and the top half is written in the language itself (Scheme, in the case of Guile) and somehow loaded by the C code when the language implementation starts.

Since 2010 or so we have been working at replacing bits written in C with bits written in Scheme. Last week's missive was about replacing the implementation of dynamic-link from using the libltdl library to using Scheme on top of a low-level dlopen wrapper. I've written about rewriting eval in Scheme, and more recently about how the road to getting the performance of C implementations in Scheme has been sometimes long.

These rewrites have a quixotic aspect to them. I feel something in my gut about rightness and wrongness and I know at a base level that moving from C to Scheme is the right thing. Much of it is completely irrational and can be out of place in a lot of contexts -- like if you have a task to get done for a customer, you need to sit and think about minimal steps from here to the goal and the gut doesn't have much of a role to play in how you get there. But it's nice to have a project where you can do a thing in the way you'd like, and if it takes 10 years, that's fine.

But besides the ineffable motivations, there are concrete advantages to rewriting something in Scheme. I find Scheme code to be more maintainable, yes, and more secure relative to the common pitfalls of C, obviously. It decreases the amount of work I will have when one day I rewrite Guile's garbage collector. But also, Scheme code gets things that C can't have: tail calls, resumable delimited continuations, run-time instrumentation, and so on.

Taking delimited continuations as an example, five years ago or so I wrote a lightweight concurrency facility for Guile, modelled on Parallel Concurrent ML. It lets millions of fibers to exist on a system. When a fiber would need to block on an I/O operation (read or write), instead it suspends its continuation, and arranges to restart it when the operation becomes possible.

A lot had to change in Guile for this to become a reality. Firstly, delimited continuations themselves. Later, a complete rewrite of the top half of the ports facility in Scheme, to allow port operations to suspend and resume. Many of the barriers to resumable fibers were removed, but the Fibers manual still names quite a few.

Scheme read, in Scheme [#279]

December 22, 2024
Andy Wingo

这给带来了我们今天的记录：我刚刚在 Scheme 中也重写了 Guile 的 reader！reader 是获取字符流并将其解析为 S 表达式的部分。以前是C语言，现在是 Scheme。

Which brings us to today's note: I just rewrote Guile's reader in Scheme too! The reader is the bit that takes a stream of characters and parses it into S-expressions. It was in C, and now is in Scheme.

这样做的主要动机之一是希望使 read 可挂起。通过此更改，现在可以在 fibers 上实现 REPL（读取-评估-打印循环）。

One of the primary motivators for this was to allow read to be suspendable. With this change, read-eval-print loops are now implementable on fibers.

Another motivation was to finally fix a bug in which Guile couldn't record source locations for some kinds of datums. It used to be that Guile would use a weak-key hash table to associate datums returned from read with source locations. But this only works for fresh values, not for immediate values like small integers or characters, nor does it work for globally unique non-immediates like keywords and symbols. So for these, we just wouldn't have any source locations.

A robust solution to that problem is to return annotated objects rather than using a side table. Since Scheme's macro expander is already set to work with annotated objects (syntax objects), a new read-syntax interface would do us a treat.

With read in C, this was hard to do. But with read in Scheme, it was no problem to implement. Adapting the expander to expect source locations inside syntax objects was a bit fiddly, though, and the resulting increase in source location information makes the output files bigger by a few percent -- due somewhat to the increased size of the .debug_lines DWARF data, but also due to serialized source locations for syntax objects in macros.

Speed-wise, switching to read in Scheme is a regression, currently. The old reader could parse around 15 or 16 megabytes per second when recording source locations on this laptop, or around 22 or 23 MB/s with source locations off. The new one parses more like 10.5 MB/s, or 13.5 MB/s with positions off, when in the old mode where it uses a weak-key side table to record source locations. The new read-syntax runs at around 12 MB/s. We'll be noodling at these in the coming months, but unlike when the original reader was written, at least now the reader is mainly used only at compile time. (It still has a role when reading s-expressions as data, so there is still a reason to make it fast.)

As is the case with eval, we still have a C version of the reader available for bootstrapping purposes, before the Scheme version is loaded. Happily, with this rewrite I was able to remove all of the cruft from the C reader related to non-default lexical syntax, which simplifies maintenance going forward.

An interesting aspect of attempting to make a bug-for-bug rewrite is that you find bugs and unexpected behavior. For example, it turns out that since the dawn of time, Guile always read #t and #f without requiring a terminating delimiter, so reading "(#t1)" would result in the list (#t 1). Weird, right? Weirder still, when the #true and #false aliases were added to the language, Guile decided to support them by default, but in an oddly backwards-compatible way... so "(#false1)" reads as (#f 1) but "(#falsa1)" reads as (#f alsa1). Quite a few more things like that.

All in all it would seem to be a successful rewrite, introducing no new behavior, even producing the same errors. However, this is not the case for backtraces, which can expose the guts of read in cases where that previously wouldn't happen because the C stack was opaque to Scheme. Probably we will simply need to add more sensible error handling around callers to read, as a backtrace isn't a good user-facing error anyway.

好吧，今晚的闲聊已经够多了。祝大家 happy hacking，晚安！

OK enough rambling for this evening. Happy hacking to all and to all a good night!