《回忆 CPSer》http://t.cn/A6Yj3WjI

CPSer 也就是人称“王垠 40 行代码”，是我在 IU 的时候自己独立想出来的“自动 CPS 变换”，而且它没有所谓 administrative redex。换言之，就是生成的代码没有多余的开销。

CPSer 本来是 Dan Friedman 给我们的一个“Brain Teaser 练习”。我辛辛苦苦花了一周时间独立写出来之后，发给 Friedman，结果他都懒得看我的代码。他以为我没什么机会直接做对，所以给我一篇 30 多页的 paper（Olivier Danvy and Andrzej Filinski: Representing Control: A Study of the CPS Transformation），让我去看。

这篇 paper 就是这个“无 administrative redex 自动 CPS 变换”的来源，但作者是从几十年前最老的 Gordon Plotkin CPS 变换出发，经过了太多聪明的“优化”之后得到的。因为我直接得到了他最后的结果，所以我没有心思去看他是怎么一步步从复杂做法得出结果。我并没有认真去读这篇论文，到现在这篇论文还看得我眼花。

因为历史上太多学生（包括我的所有同届博士生同学）做这个练习，都自称写出了 CPSer，结果却都是错的，所以 Friedman 对我声称“独立写出来”也不以为然，他开头以为我肯定也是错的。经历过太多“狼来了”的故事，他已经不相信任何学生能自己把它想出来。毕竟，人家是经过了十多年研究，写了 30 多页的 paper 才说清楚的事情，哪能让你才上第一门课，中间一周就写出来的？

然而我的 CPSer 却是正确的。我很清楚它是正确的，因为我已经把之前手动 CPS 的作业放进去过，它会输出像手写 CPS 代码一样的结果，没有任何多余的部分，而且运行结果正确。它不但是正确的，而且我的思路是直接的。我从来没有写出过 Gordon Plotin 最早的，有很多 administrative redex 的 CPSer，也就是 Danvy 和 Filinski 那篇论文的出发点。

但我有点画蛇添足，因为我的 CPSer 不但能转换 lambda calculus，而且能把完整的 Scheme 代码转换成能运行的 CPS 代码。为此我需要实现针对多参数函数，begin 等构造的转换，而不只是简单的单参数 lambda calculus 函数。

Friedman 的练习说明只说写一个 CPSer，并没说他其实只要求转换 lambda calculus。所以当我把代码给他看的时候，他看都没看就给我打回来，说“太复杂了”。经过一番争辩之后，我才发现原来他只要求我们转换 lambda calculus。于是我就把它删减到只转化 lambda calculus，还加了一点点优化，最后就只剩下 40 行了。

又过了一段时间，Friedman 终于看了我简化后的代码，才认识到我做的是对的。他让我在 B621 （高级编程语言课）上讲我的代码，告诉同学们认真听，对大家说：“好好听，Yin 这个代码价值 100 美元！”

它的价值显然不止 100 美元。后来上 Kent Dybvig 的编译器课，大家都跟着他的方法写转换的时候，我用 CPSer 的思维方式，用一个 pass 就做出了他们好几个 pass 才能完成的变换，而且还顺带实现了他们没法完成的优化。注意其实我不是直接用的 CPS，而是用的它的“思路”，我在编译器里写的东西更像是“ANF 变换”。

逃不掉的 CPSer 思路

2022 年疫情封控期间，我开进阶班讲 CPSer 的时候，自己又去看了一下 IU 的新编译器课程的录像。Kent Dybvig 已经不教课了，是 Jeremy Siek 主讲的。Jeremy Siek 当年也是从 Dybvig 的课程学会的编译器，所以他是按照 Dybvig 的方式来讲课的。当然，他不会假设同学能理解 CPSer。他自己理不理解 CPSer 都是个问题。😄

那我为什么看这录像呢？因为我想复习一下编译器，而且我想知道我上编译器课的时候是不是有点发挥过度，拿着锤子看什么都是钉子。也许其实不用 CPSer 的思路也能写出编译器，而且更简单呢？

当年 Dybvig 的课程助教 Andy Keep 每次看我的作业都头大，后来有次他不经意地提到“一堆复杂烧脑的 evaluation context”，显然就是在说我的代码。所以我后来想，也许他们的做法其实比我的简单呢？也许 Dybvig 在这里其实高我一招呢？世界上这么多编译器，他们的作者显然不懂什么 CPSer，所以不懂 CPSer 应该也能写出编译器来才对啊。也许我当时是 over-engineer 了。

所以我看了一些 Jemery Siek 的课程录像。的确，他的第一步是简单的，根本不需要 CPSer 的思路。但它的变换只得到一个转换到一半的中间结构。我以为从这个中间结构到最后的结果不会很麻烦，结果我错了。接下来的几节课的内容，我就看糊涂了。

因为第一步得到的中间结果，和后来的中间结果，都是一些“没有原则的构造”，所以到后面你就搞不清楚他在做什么了。恍惚中我发现，他后来的某个步骤中，其实用很笨的办法实现了本质是 CPSer 的变换。所以，最后我发现 CPSer 的思想是必不可少的，就算你以为最开头的步骤可以更容易，到后来还是逃不掉，而且更加难以理解。

为什么没人意识到这一点呢？毕竟上过编译器课的人毕业后很少有工作写编译器的。很快也就忘光了。

所以，虽然我承认 CPSer 的思路不容易理解，但不用 CPSer 的编译器其实更难理解。然而一旦你理解了 CPSer，你会发现它非常的优美和简单。

世界上还有谁真会 CPSer？

我发现极少能在网络上找到关于 CPS 变换的信息。除了 Danvy 和 Filinski 那篇看不懂的 paper，你能搜出来的可能就是 Matt Might 的 blog 文章了。他的 blog 里面又是 CPS 又是 ANF 的，写得好像自己很懂的样子。然而你能看懂他在写什么吗？不能。他只是直接给你一个最后的结果，而这可以直接从 Danvy 和 Filinski 的论文里抄来。他从来没有解释这个变换的原理，它的思路是什么。

看了他的几篇文章之后，感觉跟 ChatGPT 的输出挺像的了。这些 blog 文章好像只是为了让人们觉得他懂很多东西，很厉害，而并不是为了让人看懂。我友好地猜测，Matt Might 也许是理解 CPSer 的，他只是不想让别人看懂。

Continuation 专项班讲 CPSer 的原理

所以，大家应该明白 CPSer 的价值了，它显然不止 100 美元。没人愿意免费把它的原理放在网上。我也不愿意让人免费得到这样的知识，这就是为什么我的 Continuation 专项班是收费的。历经了这么多艰辛得到的东西，免费给别人就是对自己的不尊重。

而且 Continuation 专项班是一个有系统的设计，是循序渐进的。我不但告诉你 CPSer 的原理，而且告诉你怎么写 ANFer。这两个东西其实就是编译器的精髓。

当然，Continuation 专项班不止讲 CPS 变换，而且包含了非常简单而高明的并发调度，delimited continuation 等内容。弄明白了之后，Go 语言里的 goroutine 之类都知道如何实现了。我们亲手在解释器里实现 call/cc 和 shift/reset，这都是网络上找不到的信息。

所有这些名牌大学念完博士都学不到的宝贵知识，收费还非常合理。这么好的事情，世界上还有哪里可以找到？😄