第 4 章

元语言抽象

在程序设计中，我们已经看到，专家程序员使用与所有复杂系统设计者相同的通用技术来控制设计的复杂性。他们组合基本元素以形成复合对象，抽象复合对象以形成更高级的构建块，并通过采用适当的系统结构的大规模视图来保持模块化。在说明这些技术时，我们使用 Lisp 作为描述过程和构造计算数据对象及过程的语言，以对现实世界中的复杂现象建模。然而，随着我们面对日益复杂的问题，我们会发现 Lisp，或者实际上任何固定的编程语言，都不足以满足我们的需求。我们必须不断转向新的语言，以便更有效地表达我们的思想。建立新语言是控制工程设计复杂性的有力策略；通过采用一种新语言，使我们能够用特别适合当前问题的基本元素、组合手段和抽象手段来描述（从而思考）问题，我们常常可以增强处理复杂问题的能力。¹

编程拥有众多的语言。有物理语言，例如特定计算机的机器语言。这些语言关注的是以单个存储位和基本机器指令来表示数据和控制。机器语言程序员关心的是使用给定的硬件来构建系统和工具，以实现资源受限计算的高效执行。高级语言建立在机器语言基础之上，隐藏了将数据表示为位的集合以及将程序表示为基本指令序列的关切。这些语言拥有组合和抽象的手段，例如过程定义，适用于更大规模的系统组织。

元语言抽象——建立新语言——在工程设计的所有分支中都扮演着重要角色。它对计算机编程尤为重要，因为在编程中，我们不仅能构想新语言，还能通过构造求值器来实现这些语言。编程语言的求值器（或解释器）是一个过程，当应用于该语言的一个表达式时，它执行求值该表达式所需的动作。

毫不夸张地说，这是编程中最基本的思想：

求值器，它决定了编程语言中表达式的意义，不过是另一个程序。

事实上，我们可以将几乎任何程序视为某种语言的求值器。例如，第 2.5.3 节的多项式操作系统体现了多项式算术的规则，并通过对列表结构数据的操作来实现它们。如果我们用读写多项式表达式的过程来增强这个系统，我们就得到了一个用于处理符号数学问题的专用语言的核心。第 3.3.4 节的数字逻辑模拟器和第 3.3.5 节的约束传播器本身就是合法的语言，每种语言都有自己的基本元素、组合手段和抽象手段。从这个角度来看，应对大规模计算机系统的技术与构建新计算机语言的技术融合在一起，计算机科学本身也不过是构建适当描述性语言的学科。

现在我们开始探索一种技术，即如何在其他语言的基础上建立新语言。本章将使用 Lisp 作为基础，将求值器实现为 Lisp 过程。Lisp 特别适合这项任务，因为它能够表示和操作符号表达式。我们将通过为 Lisp 本身构建一个求值器，迈出理解语言如何实现的第一步。我们的求值器所实现的语言将是我们本书中使用的 Lisp 方言 Scheme 的一个子集。尽管本章描述的求值器是为 Lisp 的特定方言编写的，但它包含了为顺序机器编写程序的任何面向表达式语言的求值器的基本结构。（事实上，大多数语言处理器在其内部深处都包含一个小型的"Lisp"求值器。）该求值器为了说明和讨论的目的已被简化，一些在生产质量的 Lisp 系统中需要包含的特性被省略了。尽管如此，这个简单的求值器足以执行本书中的大多数程序。²

将求值器作为 Lisp 程序来访问的一个重要优势是，我们可以通过将对求值器程序的修改来描述替代求值规则。我们可以有效利用这种能力的一个地方，是在计算模型体现时间概念的方式上获得额外的控制，这正是第 3 章讨论的核心。在那里，我们通过使用流将世界中时间的表示与计算机中的时间解耦，缓解了状态和赋值的某些复杂性。然而，我们的流程序有时很笨拙，因为它们受到 Scheme 的应用序求值的约束。在第 4.2 节中，我们将改变底层语言以提供更优雅的方法，通过修改求值器来提供正则序求值。

第 4.3 节实现了一个更具雄心的语言变更，其中表达式具有多个值，而不仅仅是单个值。在这种非确定性计算的语言中，很自然地表达产生表达式所有可能值然后搜索满足某些约束的那些值的过程。从计算和时间的模型来看，这就像时间分支成一组"可能的未来"，然后搜索合适的时间线。使用我们的非确定性求值器，跟踪多个值和执行搜索由语言的底层机制自动处理。

第 4.4 节实现了一种逻辑编程语言，其中知识以关系的形式表达，而不是以输入和输出的计算形式表达。尽管这使该语言与 Lisp 或任何传统语言截然不同，但我们将看到逻辑编程求值器共享了 Lisp 求值器的基本结构。