ACM通信

实践

Meta II:数字文字资料室中的数字皮纸

文/戴夫·朗
ACM通信，2015年3月，第58卷第3期，43-48页
10.1145 / 2697401
评论

有些人通过重演滑铁卢战役或敲打燧石刀来重现历史，复兴古老的技能和物质文化。2012年的一个愉快的阴雨周末，我把目光转向了最近一点的地方，在1962年左右，遵循古老的知识传播模式，开始了一段沉思式的回溯式计算:演讲和背诵——或者更确切地说，生活在历史时代的优雅、演讲(这里的法语意思是阅读)和抄写(或者更具体地说，生活在后post、演讲和重新实现的优雅)。

幸运的是，就我的目的而言，杜威·瓦尔·肖尔的论文¹⁰在META II上，不像许多最近的数字工件，很容易作为数字扫描。

元二世是一个“compiler-compiler”,也就是说,当一个人怀疑生产编译器可能是一个相当大的项目写在assemblyand特别是如果有人在一个时代商业现成的,更别说自由和开放源码,编译器仍然是科学fictionthen瞄准一个中间目标是有意义的:小到可以使用汇编,但功能强大的足以让写什么人的目标放在第一位。

正如在登山运动的黄金时代，登山者会在尝试主要的攀登之前建立并储存一个大本营，之后的探险可以从前一个团队辛苦安装的基础设施中获益一样，通向我们现在使用的语言生态系统(只是偶尔咒骂)的道路是通过一系列更小、更容易实现的步骤完成的。Tony Brooker(他早在1958年就面临着在内存访问将引起各种各样的延迟时生成像样代码的“现代”问题)编写了编译器-编译器²(约翰逊后来更著名的一个词是“yet another”。⁶)来解决这个问题。根据Doug McIlroy的说法，Christopher Strachey的GPM(同时代的通用宏生成器宏扩展器)只有250条机器指令，但它足以支持Martin Richards的BCPL(基本组合编程语言)实现，后来激励Ken Thompson通过B引导C，最终导致我们现在认为理所当然的自托管本地代码生成工具链。

马的拉力比人大，但通过利用杠杆，阿基米德可以耐心地移动骄马无法移动的东西。META II是现场简易杠杆的一个很好的例子:人们可以看到梁是如何大致附着在支点上的，并感受到整个结构是如何比人们希望的更有弹性，但最终，无论多么粗糙，它都能以最少的繁琐完成工作。

回到顶部

为什么要学习META II?

1. 没有太多东西值得研究。
2. 没有太多需要检查的内容，因为它的各个部分都是简单定义的。
3. 它能产生重大的后果。

我将不详细说明，因为几乎所有对这个练习的兴趣都来自于自己动手。编程(不受经济因素的限制，就像在我们的职业中经常发生的那样)不是一项观赏性的运动。唐纳德•克努斯(Donald Knuth)说，简单的一次装配应该是一个下午的手指锻炼，他可能希望制定一些额外的计划来打发周末时间;如果你必须首先刷新大学编译课程的模糊记忆，可能要花上四五个晚上。相反，我将描述我上升的大致路线，以及为什么我确信自己到达了肖尔在我出生前描述的那个高峰。通过跟随肖尔的文本，可能还会得到我的帮助，你会发现攀登这座山峰是一种简单而愉快的攀登。(对于硬核的另一种选择:遵循费曼方法，问自己一个问题:编译器的平方根是什么?然后在没有向导的情况下上山。)

---

META II是现场简易杠杆的一个很好的例子:人们可以看到梁是如何大致附着在支点上的，并感受到整个结构可能比人们想的更有弹性，但最终，它服务于以最小的小题大做完成工作。

---

乍一看，肖尔的文章似乎天真得可怕。我们得益于半个世纪的经验和不同的词汇。然而，就像我们的父亲在我们14岁到21岁这段时间里似乎学到了很多东西一样，当我们追随肖尔的脚步时，很容易钦佩他所取得的成就。

题外话:在研究关于马的中世纪文献时，很明显，尽管马术在其间的几个世纪里几乎没有改变，兽医科学却取得了巨大的进步。有了艺术和技术之间的这种区别，并且感谢Schorre的文本，虽然是打字机字体，但既不是中世纪法语，也不是手写的，更糟糕的是，Frakturwe可以利用后见之明将信息从IBM 1401上运行的技术产物中分离出来(题外话结束)。

以下是其中一些更引人注目的段落:

• 虽然可以递归地定义序列，但使用一个特殊的运算符来实现这一目的更方便和有效。事后，我们微笑着点头，因为我们认出了克林明星(参见“汤普森建筑”基础设施)。
• 这些汇编程序都有相同的格式，显示为:标签编码地址16 810 1270。

长大后固定列格式的流行,我被介绍给别人的概念可能会以其他方式计算在高中暑期工作:在试图编写一个CMS PL / I“hello world”,我不得不引进更年长、更睿智帮助他摇着头,抚摸他们的胡子,并严肃地告诉我所有需要做的就是将我的代码对一个或两个空间,所以将不再开始,这明显是“评论”专栏。

• 重复执行，无论是递归的还是外部启动的，都会导致生成的标签的连续序列。因此，所有的语法方程都属于同一个序列。”在现代风格中，甚至在20世纪60年代末，如果你是Rod Burstall(他的笛卡尔产物⁴)，你可以称之为单体组合。在小记忆和线性卡组的时代，扁平序列是标准而不是例外，在我们的时代Rick Hehner的纸牌组⁵是一个很好的例子，在这个例子中，扁平化可以使“形式方法”的公式比通常的嵌套集更容易操作。

请注意，Schorre只用了两页就描述了我们对META II需要什么。本文的其余部分将重点介绍VALGOL，这可能是另一个合适的话题。不过，让我们暂停一下，看看以下几点:

• VALGOL I和VALGOL II中省略语句标签对大多数程序员来说似乎很奇怪。这样做并不是因为它们的实现有任何困难，而是因为作者不喜欢语句标签。我已经编程好几年了，没有使用任何标签，所以我知道从实践和理论的角度来看，它们都是多余的。然而，要在这里为这一点辩护就太离题了。”历史证明，这种离题是多余的;的确，现在看来很奇怪，因为当时看起来很奇怪。颞变形，腮内无变形(时代在变，我们也在变)。
• 最后，Schorre讨论了备份与不备份的问题，这仍然是一个当前的主题，最近流行的解析表达式语法(PEG)和其他解析器将证明这一点。然而，在我们的时代，我们对避免备份不是那么感兴趣，而是对避免从头开始，线性处理直到我们到达终点的需要感兴趣。对于编译器作者来说幸运的是，一个结果是否能被空字符串匹配是一个可以通过分治法来确定的属性……但这是为数不多的¹处理起来如此简单。

问题的核心在原文“用自己的语言编写的META II编译器”中的图5和图6 (图1)和“META II机器的订货清单”(图2，图3,4这里)。现在，我们当然可以直接效仿Schorre的做法，使用传统的引导方式:

0. 手工编写META II机器，这基本上是一个类似汇编程序的虚拟机:换句话说，一个美化的左折(我的是大约66行Python)。
1. 手工翻译META II产品到机器语言(211行m2vm操作码)。
2. 将META II产品机器翻译成机器语言(使用第1步的输出)。

请注意，Schorre的字符集不包括“;”，因此他的准bnf (Backus-Naur形式)被写在序列“.，”中。那些寻找真实感的人可能希望使用键盘午餐模拟器来创建一个“甲板”图1．然而，提前打字是不合时宜的，所以如果你要穿紧身衣，最好还是试着说服别人做你的键盘操作员。

在谴责APL过于简洁之前，您可能希望记住它是在标准字符集之前形成的，并且在110波特的情况下，您有更多的时间来考虑输入的每个字符，而不是使用自动完成的IDE(集成开发环境)。在谴责帕斯卡过于冗长之前，你可能希望回忆一下瑞士键盘的键帽有五个英语元音，以及法语重音元音和德语变音元音，因此没有提供那么多标点符号。在谴责Python和Haskell对空格的敏感之前，请回忆一下Peter Landin在1966年提出的“越位规则”，⁷它“基于垂直对齐，而不是字符宽度，因此同样适用于手写、排版或打字文本。”这不仅在用变宽字体表示代码方面具有先见之明，而且大概也迎合了当时常见的情况，即一个人敲开由另一个人在编码表上手写的代码。

正如Schorre自己所指出的，由于这个过程的固定性，如果幸运的话，它可以原谅人为错误:“总是有人问编译器是否真的生成了我手工编写的程序，我不得不说它‘几乎’是同一个程序。我遵循语法方程，试着写出编译器将要生成的内容。不幸的是，我忘记了一个多余的指令，所以结果不太一样。当然，当第一个机器编译器第二次编译自己时，它完全复制了自己。”

然而，由于懒惰，我选择在上升过程中走回头路，通过Python进行引导。正如Jungfraujoch或Klein Matterhorn现在可以通过缆车而不是步行来接近，我们可以利用字符串和命名元组库的设施来接近相同的观点，几乎没有上气不吁吁的危险。我首先建立的管道结构如下:

0. 词法分析(逐个字符的输入字符串展开为标记和文字字符串序列)。
1. 语法分析(将线性词汇表展开为语法树)。
2. 代码生成(以传统的语法导向风格)。

根据您的编程亚文化，您可能更喜欢这样称呼它syntax-directed翻译,一个访问者模式，甚至是代数同态．不管叫什么，这个问题的本质是一个组合的映射可以用映射的组合来表示，我们用这个分配的性质来分而治之(这个建议可能是亚里士多德传给亚历山大的，因为在某些事情上，古人至少比Hoare和Blelloch早了几千年)，把翻译的问题推到我们语法树的叶子上，并把结果串联起来，从而将树折叠回一个输出字符序列。

每个阶段都是由结构转换驱动的:前两个步骤采用输入中隐式的结构并将其显式化，而最后一个步骤使用该显式结构指导翻译，但随后将其忘记，使结构隐式地保留在生成的代码字符串中。如果我们包含一个链接阶段(在这个阶段中，我们将关注将生成的代码平面化成逐字序列)，结构的构建和分解将几乎是完美对称的。

注意，您可以很容易地在词法分析上抄近路。Schorre指出，“在ALGOL中，字符串被开始和结束的引号包围，这使得在字符串中有引号成为可能。键盘上的单引号是唯一的，限制了引号中的字符串不能包含其他引号。”因此，一个位的奇偶校验值就足以确定任何给定的非引号字符是在字符串内部还是外部。

当涉及到数字文字时，Schorre更加节俭:“数字的定义已经发生了根本性的变化。这样做的原因是为了减少识别数字的机器子程序所需的空间。”将Schorre的决定与Chuck Moore的《编程一种面向问题的语言》中的决定进行比较⁸举个例子，当我们的祖先必须在这些，按照目前的标准，微小的机器上实现它们时，他们准备在文字格式上花多少心思。(这种节俭让人想起了罗马人，据说，在结束第一次布匿战争的谈判中，他们在安排招待迦太基代表团的每个人中间，放了一套银器。)

语法分析还可以有效地抄近路。在尝试建立一个能够处理语法输入的系统时，您实际上并不需要完整的机器来分析您开始使用的语法。事实上，如果您愿意忽略一些无用的东西，图5中的语法可以完全通过优先级爬升(使用“”)被解析为表达式。，"， "="和"/"是二进制运算符，"＄“而且”.OUT“一元。

这些情况都是很好的例子的引导时一般原则:因为你是最初没有创建大教堂,而只是把短暂的脚手架,可以节省大量的精力做不可避免的工作(虽然仍在低水平,一切都是相对困难的)在一个快速和肮脏的方式,允许您所需的工作后以适当的方式(可能更容易,一旦你有了一个更高级别的系统的操作)。Schorre的论文以这种方式又走了两个步骤，从META II到VALGOL I再到VALGOL II，这一切都在短短几页的时间内完成。

我选择这条路线(而不是Schorre的直接上升路线)的另一个原因是，我拥有从以前的项目中遗留下来的优先级攀登解析器的框架(就像发现前一次探险留下的固定线一样);因此，解析Schorre的表达式只是更改运算符表的问题。在这种情况下，我的运气是受到了Martin Richard的简单解析器的启发⁹；Richards是通过虚拟机移植和分发技术的先驱，他的表达式解析器通常都在十来行以下;我的是在sed (1)，因此(避开了整数算术)是相对臃肿的:一行的分数。

在这一点上，我已经爬了一点，可以满意地向下看下面的山谷，但这个转弯意味着我已经从原来的上升线移动了很多。我正在解析Schorre的原始文件并生成代码，但代码是为他的虚拟机(虚拟机)编写的，我还没有重写。同样，我没有直接瞄准山顶，而是走了另一条弯路。在这种情况下，它是重写Schorre的语法来生成Python代码，而不是META II。这是良好的中间位置的另一个无价的属性:我还没有正确地重构Schorre的系统，但已经有足够的机制来按计划使用它，就像一颗种子，可以以不同的方式展开，以解决各种编译问题。

果然，肖尔的系统非常灵活，可以用一种直到四分之一个世纪后才开始使用的语言生成代码。因为额外的.LABELs对于导入样板，又进行了扩充EX2来EX2而且EX25因此，我可以简单地用Python将META II的顺序组合表示为带有标识符(True)的短路连接(and)， Python生成的META II语法增长到33行，而不是30行。现在我需要用Python实现META II VM的功能。这样做的好处是，通过生成Python代码，我可以使用完整的高级语言实现每一部分，本质上是一种“大步骤”语义的形式。它由大约85行代码组成，主要是通过迭代地重新运行程序和在执行到必要的时候实现每个操作的无脑方法开发的。调试空程序并不符合每个人的口味，但正如A.N.怀特黑德(A.N. Whitehead)所说:“文明的进步是通过扩展我们无需思考就能执行的重要操作的数量来实现的。”思想的行动就像战场上的骑兵冲锋，它们的数量是有严格限制的，需要新鲜的马匹，只有在决定性的时刻才能发动。”¹⁴

在这一点上，我能够使用python生成的META II来重新生成自身。这与直接到达顶峰的路线仍然有很大的横向距离，但它给了我信心，我正朝着正确的方向前进，也许更重要的是，我有更多的机会使用生成的Python代码，而不是Schorre的META II VM生成的代码。

最重要的是，我现在很清楚哪些数据结构是必需的，以及它们如何组合在一起。(编程词汇的变化就像裙摆的升降一样频繁，但结构化数据的重要性始终不变;弗雷德里克·布鲁克斯(Frederick P. Brooks)用他那个时代的语言说过:“给我看你的流程图，把你的表格藏起来，我就会继续迷惑不解。”给我看看你们的表格，我通常就不需要你们的流程图了;它们会很明显。”^3.在他之前，约翰·冯·诺伊曼(John von Neumann)在1947年的流程图中不仅描绘了控制流，而且一丝不苟地跟踪了表示的变化¹³)。有了这种结构，很明显可以使用Schorre的VM操作码列表并创建Python版本。由于积累了一些经验，这个版本不仅更简洁，而且更简短。结果证明，Schorre的每个操作码都可以在一到三行Python代码中简单实现，因此这是一个相对轻松的过程。我有效地实现了小步骤语义，而不是大步骤。从某种程度上说，人们可以直接从论文中按照肖尔的描述到达这里，这种弯路是在浪费时间。然而，我发现这种转移很有用，因为我不需要从头开始研究小步骤的语义，也不需要阅读和理解Schorre所写的内容，每一步的方向(就像我在沿着一条路标一样)几乎都是由给出的数据所决定的。

到这个时候，我似乎已经达到了一个顶峰。在远处，我可以看到Schorre讨论过的其他山峰，VALGOL I和VALGOL II，以及一整条不同的山峰链，它们可能对现代人的感官更有吸引力。但我怎么能确定(特别是当乌云密布，又没有一本关于巅峰的书)我正站在半个世纪前肖尔所处的地方呢?这是我第一次真正需要使用一些智慧，幸运的是，我知道自我繁殖系统是固定的点，因此引导过程应该收敛。那就不需要什么智力了:你只需要确认肖尔的程序正在运行图1通过给机器的程序图24繁殖¹²本身。事实上，如果你遵循与我类似的一组回归线，你会发现所有的可能性都汇聚在一起:不仅META II通过META II自我复制，而且Python通过Python(如上所述)自我复制，而且两个交叉项也验证了:META II通过Python产生的输出与META II通过META II产生的输出相同，而Python通过META II与Python通过Python相同。

注意自我繁殖的重要性。找到自我参照系统并不难:我们可以看看1839年的一幅用提花编织的肖像，描绘的是发明家约瑟夫·玛丽·雅卡尔(Joseph Marie Jacquard)坐在他的工作台前，手里拿着一堆打孔卡片，或者虚构的男爵Münchhausen用他的辫子把自己拉起来(而不是用他的手;他需要举起他的马和他自己，bootstrap从来不是一个选项——他寻求一个最大而不是最小的固定点)作为有趣的例子，但META II是一个有用的自我参照的例子:它几乎所有的力量，无论是在易于传播和易于扩展方面，都来自于自适用:来自于作为一个编译器的平方根。

这次演习取得了什么成果?它产生了一个自我复制的系统，在最初的META II VM(从最初的清单中工作)和Python或其他现代语言上执行。显然，我可以使用从Python引导到META II机器的相同过程，不仅可以移植到另一种底层技术，还可以实现自托管。不太明显的是，我解决的基本问题是(以一种“好”的方式)将一个Kleene代数(由序列、交替和重复组成)转换为另一个Kleene代数，这是一种模式，即使在计算中不是无处不在，但在处理比线性数据“购物清单”更有结构的东西时肯定是常见的。比较Thompson的NFA(非确定性有限自动机)结构¹¹在这种方法中，搜索问题通过解析规范来解决，然后在虚拟(非确定性)机器上执行该规范，并将非确定性虚拟代码进一步编译为实际的确定性机器代码。

最后，记住META II非常适合这类练习，因为它被设计成引导的。正如Schorre在他的介绍中所说:“META II并不是一种每个人都会用来编写编译器的标准语言。相反，它是一个简单工作语言的例子，可以为设计编译器提供一个良好的开端——编写适合自己需要的编译器。事实上，META II编译器是用自己的语言编写的，因此可以进行修改。”

我希望实现您自己的META II的练习不仅会有提供一个容易修改的“工作台”来更好地解决您自己的问题的短期好处，而且还会有一个长期的好处，在一定程度上，您可以安排功能易于引导，您可以帮助减轻信息技术的“永久重写本”，其中比特rot的悖论意味着许多工件有效的半衰期甚至比口述历史更短。

毕竟，野蛮人可能完全适应他们所处的环境，但要成为文明的一部分，就要知道在其他地方和其他时代的其他人是如何做事的，因此要知道自己所做的事情有多少是必要的，有多少是偶然的。更具体地说，野蛮人必须从自己的错误中吸取教训;文明人可以从别人的错误中吸取教训。非常具体地说，对于面临短暂需求的工程师来说，避免将手边的代码库看作是一个本身的东西，而只是将其视为相关可能程序的类的一个特定实例化，这通常是有帮助的。

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2015 ACM, Inc.

---

没有找到条目