第 1 章

用过程构建抽象

我们将要研究计算过程的概念。计算过程是存在于计算机中的抽象存在。随着它们的演化，过程操纵着称为数据的其他抽象事物。过程的演化由称为程序的规则模式所引导。人们创建程序来指导过程。实际上，我们用咒语召唤计算机中的精灵。

计算过程确实很像巫师心目中的精灵。它不能被看见或触摸，根本不由物质组成。然而，它非常真实。它可以从事智力工作，可以回答问题。它可以通过在银行支付款项或控制工厂的机器人手臂来影响世界。我们用来召唤过程的程序就像巫师的咒语。它们由神秘而深奥的编程语言中的符号表达式精心构成，这些语言规定了我们希望过程执行的任务。

在正常工作的计算机中，计算过程精确而准确地执行程序。因此，就像巫师的学徒一样，新手程序员必须学会理解和预见他们召唤的后果。即使是程序中的小错误（通常称为bug 或 glitch）也可能产生复杂而不可预见的后果。

幸运的是，学习编程比学习巫术要安全得多，因为我们所处理的精灵被以安全的方式方便地容纳着。然而，现实世界的编程需要细心、专业知识和智慧。例如，计算机辅助设计程序中的一个小错误，可能导致飞机或大坝的灾难性坍塌，或者工业机器人的自毁。

优秀的软件工程师有能力组织程序，使他们对最终过程将执行预期任务有合理的把握。他们可以预先可视化系统的行为。他们知道如何构建程序，使未预见的问题不会导致灾难性后果，并且当问题出现时，他们可以调试程序。精心设计的计算系统，就像精心设计的汽车或核反应堆一样，是以模块化方式设计的，这样各个部件可以分别构建、替换和调试。

用 Lisp 编程

我们需要一种合适的语言来描述过程，我们将为此使用 Lisp 编程语言。就像我们的日常思想通常用自然语言（如英语、法语或日语）表达，定量现象的描述用数学符号表达一样，我们的程序性思想将用 Lisp 表达。Lisp 发明于 1950 年代末，是一种用于推理使用某种称为递归方程的逻辑表达式的形式体系，作为计算的模型。该语言由 John McCarthy 构想，基于他的论文〈符号表达式的递归函数及其机器计算〉（McCarthy 1960）。

尽管 Lisp 最初是作为一种数学形式体系而诞生的，但它也是一种实用的编程语言。Lisp 解释器是一种执行用 Lisp 语言描述的过程的机器。第一个 Lisp 解释器由 McCarthy 在同事和学生的帮助下实现，他们来自 MIT 电子研究实验室人工智能组和 MIT 计算中心。¹ Lisp 的名称是 LISt Processing（列表处理）的缩写，设计目的是提供符号操作能力，以解决诸如代数表达式的符号微分和积分等编程问题。为此，它包含了称为原子和列表的新数据对象，这使它显著区别于该时期的所有其他语言。

Lisp 并非有意识设计的产品。相反，它是以实验方式根据用户需求和实际实现考虑非正式地演化而来的。Lisp 的非正式演化多年来一直持续，Lisp 用户社区传统上抵制任何推广语言"官方"定义的尝试。这种演化，加上初始概念的灵活性和优雅性，使 Lisp——目前仍在广泛使用的第二古老的语言（只有 Fortran 更古老）——能够不断适应并包含关于程序设计的最现代思想。因此，Lisp 现在已经是一个方言家族，虽然共享大多数原始特征，但在重要方面可能彼此不同。本书中使用的 Lisp 方言称为 Scheme。²

由于其实验性质和对符号操作的强调，Lisp 最初在数值计算方面非常低效，至少与 Fortran 相比是这样。然而，多年来，人们开发了 Lisp 编译器，可以将程序翻译成能够相当高效地执行数值计算的机器代码。对于特殊应用，Lisp 已被非常有效地使用。³ 尽管 Lisp 尚未完全摆脱被认为毫无希望地低效的旧名声，但 Lisp 现在被用于许多效率并非核心关注点的应用。例如，Lisp 已成为操作系统 shell 语言以及编辑器和计算机辅助设计系统的扩展语言的首选语言。

如果 Lisp 不是主流语言，为什么我们要把它作为讨论编程的框架？因为该语言拥有独特的特性，使其成为研究重要编程构造和数据结构的优秀媒介，并能将它们与支持它们的语言特性联系起来。这些特性中最重要的是，Lisp 对过程的描述（称为 过程）本身可以作为 Lisp 数据来表示和操作。这一点的重要性在于，有一些强大的程序设计技术依赖于模糊"被动"数据和"主动"过程之间的传统区别。正如我们将要发现的，Lisp 在处理过程作为数据方面的灵活性，使其成为探索这些技术的最方便的语言之一。将过程表示为数据的能力也使 Lisp 成为编写必须将其他程序作为数据来操作的程序的优秀语言，例如支持计算机语言的解释器和编译器。除了这些考虑之外，用 Lisp 编程本身也充满乐趣。