PDFMETA II：数字时代的羊皮纸，数字时代的缮写室
重温 Schorre 1962 年的编译器-编译器
Dave Long
有些人进行活态历史研究——通过重演滑铁卢战役或制作燧石刀来复兴古老的技能和物质文化。在 2012 年一个令人愉悦的雨天周末，我的目光稍微转向近代，沉浸在 1962 年左右的冥想式复古计算中，遵循古老的知识传播模式：讲座和背诵——或者更确切地说，得益于生活在历史时代，讲座（此处为法语意义上的阅读）和抄写（或者更具体地说，得益于后后现代生活，讲座和重新实现）。
幸运的是，就我的目的而言，与许多较新的数字文物不同，Dewey Val Schorre 关于 META II 的论文10很容易以数字扫描件的形式获得。
META II 是一种“编译器-编译器”，也就是说，当人们怀疑编写一个生产编译器可能是一个相当大的汇编语言项目时——尤其是在一个 COTS（商用现货）、更不用说自由和开源编译器仍然是科幻小说的时代——那么，瞄准一个中间目标是有意义的：它足够小，可以用汇编语言手工编码，但又足够强大，可以编写最初的目标。
正如登山者在登山运动的黄金时代会在尝试主峰攀登之前建立和储备一个大本营一样，后来的探险队可以从先前团队辛勤安装的基础设施中获益，我们现在使用的语言生态系统之路（只是偶尔咒骂一下）是通过一系列更小、更容易实现的步骤完成的。Tony Brooker（早在 1958 年就面临着“现代”问题，即当内存访问会产生差异很大的延迟时，如何生成像样的代码）编写了编译器-编译器2（Johnson 后来更著名的编译器是“又一个”6），以在 1960 年代初期解决这个问题。根据 Doug McIlroy 的说法，Christopher Strachey 的 GPM（通用宏生成器——同一时代的宏展开器）只有 250 条机器指令，但它足以支持 Martin Richards 的 BCPL（基本组合编程语言）实现，后来启发 Ken Thompson 通过 B 引导 C，最终导致我们现在认为理所当然的自托管本地代码生成工具链。
马可以比人拉更多东西，但通过利用杠杆原理，阿基米德可以耐心地移动 Secretariat 做不到的事情。META II 是一个很好的现场即兴杠杆的例子：人们可以看到梁是如何粗略地连接到支点的，并感觉到整个结构可能比人们希望的更具弹性，但最终，无论多么粗糙，它都能以最少的麻烦完成工作。
为什么要研究 META II？
1. 没有太多可研究的内容。
2. 没有太多可研究的内容，因为它的组成部分定义简单。
3. 它能产生重要的结果。
我不会详细介绍，因为这项练习的几乎所有乐趣都来自亲自动手。编程（当不受经济因素的约束时，就像在我们的职业中经常遇到的那样）不是一项观赏性运动。Donald Knuth 说一个简单的单遍汇编器应该是一个下午的指尖运动，他可能希望制定一些额外的计划来充实他的周末；如果你必须首先重温大学编译器课程的模糊记忆，可能需要接近四到五个晚上。相反，我将描述我攀登的大致路线，以及为什么我确信我到达了 Schorre 在我出生前很久就描述过的同一个顶峰。通过遵循 Schorre 的文本，可能在我的帮助下，您也会发现攀登这座山峰是一次轻松愉快的旅程。（对于硬核人士的另一种选择：遵循费曼方法，问自己一个问题：“编译器的平方根是什么？”然后在没有向导的情况下登上山顶）
初读时，Schorre 的文本可能显得非常幼稚。我们受益于半个世纪的经验和不同的词汇。然而，正如通常令人惊讶的是，我们的父亲似乎在我们 14 岁到 21 岁之间学到了多少东西一样，当我们追随他的脚步时，很容易钦佩 Schorre 所取得的成就。
题外话：在研究关于马匹的中世纪文本时，很明显，虽然骑术在过去的几个世纪中变化不大，但兽医学已经取得了巨大的进步。考虑到艺术和技术之间的这种区别——并庆幸 Schorre 的文本虽然是打字机字体，但既不是中世纪法语，也不是更糟糕的手写 Fraktur 字体——我们可以利用后见之明将信息学与在 IBM 1401 上运行的技术文物区分开来（题外话结束）。
以下是一些更引人注目的段落
* “尽管序列可以递归定义，但为此目的设置一个特殊运算符会更方便高效。” 事后看来，当我们认出 Kleene 星号时，我们会微笑并点头（参见. 下文的“Thompson 构造”）。
* “这些汇编器都具有相同的格式，如下所示
LABEL CODE ADDRESS 1- -6 8- -10 12- -70。”
在固定列格式普及之后长大，我在高中暑期工时接触到一个概念，即其他人可能会以其他方式进行计算：在尝试在 CMS 下编写 PL/I “hello world” 时，我不得不请来年长而明智的帮助，他们摇了摇头，捋了捋胡须，严肃地告诉我，需要做的就是将我的代码向右移动一到两个空格，这样它就不会再从显然是“注释”列的位置开始。
* “重复执行，无论是递归的还是外部启动的，都会导致生成的标签的连续序列。因此，所有语法方程都贡献于一个序列。” 在现代风格中，或者即使在 1960 年代后期，如果您是 Rod Burstall（参见他的笛卡尔积4），您可能会称其为单子组合。在内存较小且本质上是线性卡片组的时代，扁平化序列是常态而不是例外，在我们这个时代，Rick Hehner 的 bunches5 是一个很好的例子，其中扁平化可以使“形式方法”的公式比通常可嵌套的集合更容易操作。
请注意，Schorre 只用了两页就描述了 META II 所需的内容。本文的其余部分用于描述 VALGOL，这可能是另一天的合适目的地。但是，让我们稍作停顿，检查几个要点
* “从 VALGOL I 和 VALGOL II 中省略语句标签对大多数程序员来说似乎很奇怪。这样做不是因为它们的实现有任何困难，而是因为作者不喜欢语句标签。我编程了好几年，没有使用过一个标签，所以我知道从实践和理论的角度来看，它们都是多余的。尽管如此，试图在此处证明这一点是题外话了。” 历史同意题外话是多余的；的确，现在看来，当时觉得奇怪才奇怪。Tempora mutantur, nos et mutamur in illis（时代在变，我们也在变）。
* 最后，Schorre 讨论了备份与不备份的问题，这仍然是一个当前的话题，正如最近 PEG（解析表达式语法）和其他解析器的流行所证明的那样。然而，在我们这个时代，我们不太感兴趣避免备份，而是避免需要从头开始并线性处理直到结束。幸运的是，对于编译器编写者来说，一个产生式是否可以与空字符串匹配是一个可以通过分而治之确定的属性……但它是少数几个1如此简单地处理的属性之一。
问题的核心在于原始文章中的图 5 和图 6，“用 META II 自身语言编写的 META II 编译器”（本文中的图 1）和“META II 机器的指令列表”（此处的图 2 至图 4）。现在，当然可以直接跟随 Schorre 的脚步，使用传统的引导方法
0. 手工编写 META II 机器的代码——这基本上是一个类似汇编器的虚拟机：换句话说，一个美化的左折叠（我的大约 66 行 Python 代码）。
1. 手工将 META II 产生式翻译成机器语言（211 行 m2vm 操作码）。
2. 机器翻译 META II 产生式为机器语言（使用步骤 1 的输出）。
请注意，Schorre 的字符集不包含 ";>”，因此他的准 BNF（巴科斯-瑙尔范式）是用序列 "
编写的 .,>”。那些寻求真实感的人可能希望使用穿孔卡模拟器从图 1 创建一个“卡片组”。但是，预输入是过时的，因此，如果您要穿苦行衣，最好尝试说服其他人成为您的穿孔卡操作员。
在谴责 APL 过分简洁之前，您可能需要记住，它是在标准字符集之前形成的，并且在 110 波特率下，您有更多时间思考键入的每个字符，而不是使用自动完成的 IDE（集成开发环境）。在谴责 Pascal 过分冗长之前，您可能希望回想起瑞士键盘不仅有五个英语元音的键帽，还有法语带重音符号的元音以及德语变音元音的键帽，因此没有提供那么多标点符号。在谴责 Python 和 Haskell 对空格敏感之前，请回想一下 Peter Landin 在 1966 年提出了“越位规则”7，该规则“基于垂直对齐，而不是字符宽度，因此同样适用于手写、排版或键入的文本。” 这不仅对以可变宽度字体呈现代码具有先见之明，而且可能还迎合了当时常见的情况，即一个人穿孔卡片的代码是由另一个人手写在编码表上的。
正如 Schorre 自己指出的那样，由于此过程的定点性质，如果幸运的话，它可以容忍人为错误：“总有人问编译器是否真的完全生成了我手写的程序，我不得不说它是‘几乎’相同的程序。我遵循了语法方程，并尝试编写编译器将要生成的内容。不幸的是，我忘记了一条冗余指令，因此结果并不完全相同。当然，当第一台机器生成的编译器第二次编译自身时，它完全再现了自身。”
然而，由于懒惰，我选择在攀登过程中走了一条之字形路线，通过 Python 进行引导。正如少女峰或小马特洪峰现在可以通过缆车和吊船而不是步行到达一样，我们可以利用字符串和命名元组库设施以接近相同的视点，而几乎没有气喘吁吁的危险。我最初建立的管道结构如下
0. 词法分析（将逐字符的输入字符串展开为标记和文字字符串序列）。
1. 语法分析（将线性词法列表展开为语法树）。
2. 代码生成（以传统的语法制导风格）。
根据您的编程亚文化，您可能更喜欢将其称为语法制导翻译、访问者模式，甚至代数同态。无论它被称为什么，问题的本质在于组合的映射可以表示为映射的组合，我们使用这种分配律进行分而治之（亚里士多德可能将此建议传给了亚历山大——表明在某些方面，古代人比 Hoare 和 Blelloch 领先了几千年），将翻译问题推到语法树的叶子上并连接结果，从而将树折叠回输出字符序列。
每个阶段都由结构转换驱动：前两个步骤获取输入中隐含的结构并使其显式化，而最后一步使用此显式结构来指导翻译，然后忘记它，将结构隐含在生成的代码字符串中。如果我们包含一个链接阶段（其中我们将关注将生成的代码展平为逐字序列），那么结构的构建和分解将几乎完全对称。
请注意，您可以在词法分析中轻松地偷工减料。Schorre 指出，“在 ALGOL 中，字符串用开头和结尾的引号括起来，这使得在字符串中包含引号成为可能。穿孔卡上的单引号是唯一的，它限制了带引号的字符串不能包含其他引号。” 因此，一个比特的奇偶校验足以确定任何给定的非引号字符是在字符串内部还是外部。
Schorre 在处理数字字面量时甚至更加节俭：“数字的定义已得到彻底改变。这样做的原因是减少机器子例程识别数字所需的空间。” 将 Schorre 的决策与 Chuck Moore 的“面向问题语言编程”8 中的决策进行比较，以了解我们的前辈在他们的字面量格式上投入了多少思考，当他们必须在这些按当前标准来看微不足道的机器上实现时。（这种节俭让人想起罗马人，据说他们在结束第一次布匿战争的谈判期间，在所有计划接待迦太基代表团的人员之间复用了同一套银器。）
语法分析也可以有效地偷工减料。在尝试构建一个可以处理语法输入的系统时，您实际上不需要完整的机制来分析您开始使用的语法。事实上，如果您愿意忽略一些垃圾，图 5 中的语法可以完全通过优先级攀升解析为一个表达式，其中 ".,", "=>”，和 "/>” 是二元运算符，而 "$>” 和 “。OUT>” 是一元运算符。
所有这些情况都是引导时一般原则的良好示例：因为您最初不是在建造大教堂，而只是搭建临时的脚手架，所以您可以通过以快速而肮脏的方式完成不可避免的工作（同时仍然在较低级别，一切都相对困难），从而节省大量精力，从而使您以后能够以适当的方式（可能更容易，一旦您拥有一个在更高级别运行的系统）完成所需的工作。Schorre 的论文以这种方式又迈出了两步，在几页的篇幅内从 META II 发展到 VALGOL I 再到 VALGOL II。
我采取这条路线而不是 Schorre 的直接攀登的另一个原因是，我有幸（很像发现先前探险队留下的固定绳索）拥有从先前项目中遗留下来的优先级攀升解析器的骨架；因此，解析 Schorre 的表达式只是更改运算符表的问题。在这种情况下，我的幸运之处在于受到了 Martin Richards 的简单解析器9的启发。Richards 是通过虚拟机进行移植和分发技术的先驱，他的表达式解析器通常不到十几行；我的解析器是从 `sed(1)` 的重新实现中遗留下来的sed(1)，因此（由于避开了整数算术）相对臃肿：有几十行代码。
此时，我已经攀登了一段距离，可以带着些许满意地俯视下方的山谷，但是之字形路线意味着我已经从原始攀登路线横向移动了很多。我正在解析 Schorre 的原始文件并生成代码，但是代码是为他的 VM（虚拟机）生成的，我尚未重写该 VM。同样，与其直接瞄准顶峰，我不如又走了一条之字形路线。在这种情况下，它是重写 Schorre 的语法以生成 Python 代码而不是 META II。这是良好的中间位置的另一个宝贵属性：我尚未正确地重建 Schorre 的系统，但是已经有足够的机制可以使用它，作为可以以不同方式展开以解决不同类型编译问题的种子。
果然，Schorre 的系统足够灵活，可以用一种直到四分之一世纪后才开始出现的语言生成代码。由于额外的.LABELs用于导入样板代码，以及扩展EX2 到 EX2 和 EX25这样我就可以在 Python 中将 META II 的顺序组合简单地表示为短路连接（and）和恒等式（True），生成 Python 代码的 META II 语法增长到 33 行而不是 30 行。现在我需要在 Python 中实现 META II VM 的功能。优点是，通过生成 Python 代码，我可以使用完整的高级语言来实现每个部分，本质上是一种“大步”语义形式。这由大约 85 行代码组成，这些代码主要是通过迭代地重新运行程序并在执行达到必要点时实现每个操作的无脑方法开发的。调试空程序并不符合每个人的口味，但正如 A. N. Whitehead 所说：“文明的进步是通过扩展我们可以不假思索地执行的重要操作的数量来实现的。思想的运作就像战场上的骑兵冲锋——它们的数量严格限制，它们需要新鲜的马匹，并且只能在决定性时刻进行。”14。
此时，我能够使用生成 Python 代码的 META II 来重新生成自身。这仍然与直接通往顶峰的路线横向偏离了很多，但这让我确信我正朝着正确的方向前进，也许更重要的是，我使用生成的 Python 代码的频率远高于为 Schorre 的 META II VM 生成的代码。
最重要的是，我现在清楚地了解了哪些数据结构是必要的以及它们如何组合在一起。（编程的词汇变化与裙子的下摆升降一样频繁，但结构化数据的重要性仍然不变。Frederick P. Brooks 用他那个时代的语言说，“给我看你的流程图并隐藏你的表格，我将继续感到困惑。给我看你的表格，我通常不需要你的流程图；它们会很明显。3 在他之前，John von Neumann 不仅描绘了控制流程，而且还在他 1947 年的流程图中仔细跟踪了表示形式的变化13。）有了这种结构，很明显如何采用 Schorre 的 VM 操作码列表并创建 Python 版本。有了些经验之后，这个版本不仅更简洁，而且更短。事实证明，Schorre 的每个操作码都可以简单地用一到三行 Python 代码实现，因此这是一个相对轻松的过程。我有效地实现了小步语义而不是大步语义。在某种程度上，人们可以通过直接从论文中遵循 Schorre 的描述来到达这里，那么之字形路线就是浪费时间。但是，我发现这种转移很有用，因为与其从头开始研究小步语义，或者阅读和理解 Schorre 所写的内容，不如说每一步要采取的方向（就好像我正在沿着一条清晰的道路前进一样）几乎是由给定的数据强制执行的。
到这个时候，我似乎已经到达了顶峰。在远处，我可以看到 Schorre 讨论过的其他山峰，VALGOL I 和 VALGOL II，以及一系列不同的山峰，这些山峰可能对现代感性更具吸引力。但是，我怎么能确定（尤其是在云层已经来临并且没有登顶记录的情况下）我正站在半个世纪前 Schorre 站立的地方？这是我第一次可能真正需要运用一些智力，幸运的是，我知道自复制系统是定点，因此引导过程应该会收敛。那么几乎不需要智力：您只需要确认通过图 2-4 中给出的机器程序运行图 1 中的 Schorre 程序是否会再现12自身。事实上，如果您遵循与我类似的之字形路线，您会发现所有可能性都会收敛：不仅 META II 通过 META II 再现自身，而且 Python 通过 Python（如上所述）再现自身，并且两个交叉项也通过检查：META II 通过 Python 产生与 META II 通过 META II 相同的输出，而 Python 通过 META II 与 Python 通过 Python 相同。
请注意此处自复制的重要性。找到自引用系统并不困难：我们可以以 1839 年的提花织物肖像为例，该肖像描绘了发明家 Joseph Marie Jacquard 坐在他的工作台上，旁边放着一堆穿孔卡片，或者虚构的 Baron Münchhausen 通过抓住自己的辫子将自己拉起来（而不是通过他的靴子带；由于需要抬起他的马和自己，靴子带从来都不是一种选择——他寻求的是最大定点而不是最小定点）作为有趣的例子，但 META II 是自引用的一个有用例子：它几乎所有的能力，无论是传播的便利性还是扩展的便利性，都来自自适用性：来自作为编译器的平方根。
这项练习完成了什么？它产生了一个自复制系统，该系统既可以在原始 META II VM 上执行（从原始列表工作），也可以在 Python 或另一种现代语言上执行。显然，我可以使用我遵循的从 Python 引导到 META II 机器的相同过程，不仅可以移植到另一种底层技术，还可以实现自托管。不太明显的是，我解决的基本问题是以“友好”的方式将一个 Kleene 代数（由序列、交替和重复组成）翻译成另一个 Kleene 代数，这是一种模式，即使在计算中不是普遍存在的，但在我们处理具有比线性“购物清单”数据更多结构的事物时，它肯定是常见的。将 Thompson 的 NFA（非确定性有限自动机）构造11进行比较，其中搜索问题通过解析规范来解决，然后在虚拟（非确定性）机器上执行该规范，其曲折之处在于非确定性虚拟代码已进一步编译为实际的确定性机器代码。
最后，请记住，META II 非常适合这种练习，正是因为它被设计为可引导的。正如 Schorre 在他的介绍中说的那样：“META II 并非旨在成为每个人都用来编写编译器的标准语言。相反，它是一个简单的工作语言的示例，它可以为人们在设计适合自己需求的编译器编写编译器方面提供良好的开端。事实上，META II 编译器是用其自身的语言编写的，因此它本身就易于修改。”
我希望实现您自己的 META II 的练习不仅会带来短期利益，即提供一个易于修改的“工作台”，您可以用它更好地解决自己的问题，而且还会带来长期利益，因为在您可以安排功能易于引导的范围内，您可以帮助缓解信息技术的“永久羊皮纸”，其中比特腐烂的悖论意味着许多文物的有效半衰期甚至比口述历史还要短。
毕竟，野蛮人可能完全适应他们的环境，但成为文明的一部分就是要意识到其他地方和时代的人们是如何做事的，从而知道一个人自己所做的事情有多少是必要的，有多少是偶然的。更具体地说，野蛮人必须从自己的错误中学习；文明人有幸从别人的错误中学习。非常具体地说，对于面临短暂需求的工程师来说，避免将手头的代码库视为事物本身通常很有帮助，而是将其仅视为相关可能程序类别的特定实例化。
喜欢它，讨厌它？请告诉我们
参考文献
1. Backhouse, R. 2006. Regular algebra applied to language problems. Journal of Logic and Algebraic Programming 66; http://www.cs.nott.ac.uk/~rcb/MPC/RegAlgLangProblems.ps.gz.
2. Brooker, R. A., MacCallam, I. R., Morris, D., Rohl, J. S. 1963. The compiler compiler. Annual Review in Automatic Programming 3: 229-275.
3. Brooks, F. P. 1975. The Mythical Man-Month. Addison Wesley.
4. Burstall, R. M. 1969. Proving properties of programs by structural induction. Computer Journal 12 (1): 41-48.
5. Hehner, E. C. R. 1993. A practical theory of programming. Texts and Monographs in Computer Science. Springer.
6. Johnson, S. C. Yacc: yet another compiler-compiler; https://www.cs.utexas.edu/users/novak/yaccpaper.htm.
7. Landin, P. J. 1966. The next 700 programming languages. Communications of the 9(3): 157-166; http://doi.acm.org/10.1145/365230.365257.
8. Moore, C. H. 1970. Programming a problem-oriented-language; http://www.colorforth.com/POL.htm.
9. Richards, M. 2007. The MCPL Programming Manual and User Guide. 58, 63; http://www.cl.cam.ac.uk/~mr10/mcplman.pdf
10. Schorre, D. V. 1964. META II: a syntax-oriented compiler writing language. In Proceedings of the 19th National Conference: 41.301-41.3011; http://doi.acm.org/10.1145/800257.808896.
11. Thompson, K. 1968. Programming techniques: regular expression search algorithm. Communications of the 11(6): 419-422; http://doi.acm.org/10.1145/363347.363387.
12. Thompson, K. 1984. Reflections on trusting trust. Communications of the 27(8): 761-763; http://doi.acm.org/10.1145/358198.358210.
13. von Neumann, J., Goldstine, H. H. 1947. Planning and Coding of Problems for an Electronic Computing Instrument . Princeton, NJ: Institute for Advanced Study.
14. Whitehead, A. N. 1911. An Introduction to Mathematics. New York, NY: Henry Holt and Company.
Dave Long 的职业生涯始于语言工具链，从超级计算机到原型微处理器，但很快转向了消费者在线服务的黑暗面。他现在将时间分配在开发马匹区域网络传感器系统（作为当前技术在训练马匹进行千年历史的骑术比赛问题上的应用）和仅仅享受比赛之间。（这项技术并不那么先进，力反馈有时超出了人们的期望，但帧速率始终非常出色。）
© 2014 1542-7730/14/1200 $10.00
"J'ai seulement fait ici un amas de fleurs étrangères, n'y ayant fourni du mien que le filet à les lier." ("我收集了一束别人的花，除了捆绑它们的花线之外，没有什么是属于我的。") —蒙田，《随笔集》，1595 年
最初发表于《Queue》杂志第 13 卷，第 1 期—
在 数字图书馆中评论本文
更多相关文章
Matt Godbolt - C++ 编译器中的优化
在向编译器提供更多信息时，需要在编译速度方面做出权衡：这可能会使编译速度变慢。链接时优化等技术可以为您提供两全其美的效果。编译器中的优化在不断改进，即将到来的间接调用和虚函数分派方面的改进可能很快会带来更快的多态性。
Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是解决跨组件边界引用循环问题的一种方法。只要组件可以形成具有跨 API 边界的非平凡所有权的任意对象图，就会出现此问题。CCT 的增量版本在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。
David Chisnall - C 并非低级语言
在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间来研究根本原因。这两种漏洞都涉及处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的功能被添加，是为了让 C 程序员继续相信他们正在用低级语言编程，而这种情况已经几十年没有发生了。
Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库，其中许多库已知存在漏洞。了解问题的范围，以及包含库的许多意外方式，只是改善情况的第一步。这里的目标是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。
© 保留所有权利。