前言

我们都曾花费太多的时间试图改造一段旧的代码，以便能以一种编写时没有意识到的方式使用它。这是一种可怕的时间和精力上的浪费。不幸的是，对我们而言，要为一个非常具体的目的写出特别好用的代码，并且很少有可重复使用的部分，是一件很有压力的事情。但我们认为，这并不是必要的。

我们很难建立一个系统，使其在比设计者预期的更大范围内具有可接受行为。最好的系统是可进化的，只需稍加修改就能适应新的环境。我们怎样才能设计出具有这种灵活性的系统呢？

如果我们为程序添加一个新的功能时所要做的就只是添加一些代码，而不改变现有的代码库，那就太棒了。我们通常可以通过在构建代码库时使用特定组织原理，同时加入适当的钩子（hook）来实现这一目的。

对生物系统的观察告诉我们很多关于如何建立灵活和可进化系统的知识。最初为支持符号人工智能而开发的技术通常被认为可以提高程序和其他工程系统灵活性和适应性。相比之下，计算机科学的普遍做法是不鼓励构建便于在新环境中使用的易于修改的系统。

我们的编程经常把自己逼到死胡同里，不得不花大力气重构代码以摆脱这些死胡同。现在，我们已经积累了足够的经验，可以识别、分离并展示我们发现的对构建大型系统有效的策略和技术，这些策略和技术可以适应原始设计中没有预料到的目的。在本书中，我们分享了多年编程经验总结而成的一些成果。

关于本书

本书是为了在麻省理工学院教授计算机程序设计而编写的。我们在多年前就开设了这门课，打算让高年级本科生和研究生了解用于构建人工智能应用的核心程序的有效技术，如数学符号操作和基于规则的系统。

我们希望学生能够灵活地建立这些系统，这样就可以轻松地将这些系统组合起来，从而形成更强大的系统。我们还想让学生了解依赖关系，包括如何跟踪它们以及如何利用它们来解释和控制回溯。

虽然这门课过去和现在都很成功，但事实证明，一开始我们对这门课的理解并不像我们最初认为的那样深入。因此，我们投入了大量的精力来推敲打磨，使我们的想法更加精确，并且意识到这些技术不仅可以用于人工智能应用。任何正在构建复杂系统（如计算机语言编译器和集成开发环境）的人，都会从我们的经验中受益。本书是由我们的课程中正在使用的讲义以及问题集整理而成的。

主要内容

本书中的内容比一个学期课程所能涵盖的知识更加丰富。因此，我们每次上课时都会挑选部分内容进行讲解。第1章是对编程哲学的介绍。我们在自然和工程的大背景下提出了灵活性的概念，并试图说明灵活性是与效率和正确性同样重要的问题。在随后的每一章中都介绍了一些技术，并通过一组练习来说明这些技术。这是本书的一个重要组织原则。

在第2章中，我们探讨了用一些普遍适用的方法构建易于扩展的系统。组织灵活系统的一个强有力的方法是把它建成特定领域语言的集合体，每一种语言都适合轻松表达一个子系统的构造。我们设计了开发特定领域语言的基本工具，展示了如何围绕混合-匹配组件来组织子系统，如何用组合器来灵活地组合它们，如何用包装器来泛化组件，以及如何通过抽象出领域模型来简化程序设计。

在第3章中，我们介绍了极其强大但有潜在危险的灵活性技术——谓词调度的通用程序。我们从泛化算术以处理符号代数表达式开始，展示如何通过使用数据的类型标记使这种泛化变得高效。我们通过设计一个简单但易于详细说明的冒险游戏来展示该技术的能力。

在第4章中，我们介绍了符号模式匹配，首先启用了术语重写系统，然后通过合一展示了类型推理是如何轻松实现的。在这里，我们遇到了由于段变量而需要进行回溯的问题。合一是我们看到表示和组合部分信息结构的力量的第一个地方。在本章的最后，我们将这个想法扩展到匹配一般的图上。

在第5章中，我们探讨了解释和编译的力量。我们认为，程序员应该知道如何摆脱他们必须使用的任何编程语言的束缚，为一种更适合表达当前问题的解决方案的语言制作一个解释器。我们还展示了如何通过在解释器/编译器系统中实现非确定性的amb来自然地纳入回溯搜索，以及如何使用连续。

在第6章中，我们展示了如何构造分层数据和分层程序的系统，其中每个数据项都可以用各种元数据进行注释。底层数据的处理不受元数据的影响，处理底层数据的代码甚至不知道或已引用元数据。然而，元数据是由它自己的程序处理的，有效地与数据并行。我们通过给数字量附加单位来说明这一点，并展示如何携带依赖性信息，就像从原始来源得到的那样给出数据的出处。

前面所述的一切都汇集在第7章，在这章我们引入了传播，以摆脱计算机语言的面向表达式范式。在这章，我们有一个将模块连接在一起的布线图设想，允许灵活地纳入部分信息的多个来源。使用分层数据来支持对依赖关系的跟踪，可以实现依赖定向回溯，从而大大减小大型复杂系统的搜索空间。

本书可用于各种高年级课程，在随后的所有章节中都使用了第2章介绍的组合器思想和第3章介绍的通用程序，但是第4章的模式和模式匹配以及第5章的评估器并没有在后面的章节中使用。第5章中唯一用于后续章节学习的材料是5.4节中对amb的介绍。第6章中的分层思想与通用程序的想法密切相关，但有一个新的变化。在第6章中，作为一个例子，介绍使用分层来实现依赖性跟踪，这已成为传播（见第7章，使用依赖性来优化回溯搜索）中的一个重要组成部分。

Scheme编程语言

本书中的代码是用Scheme写的，作为Lisp的变种，Scheme是一种功能语言。虽然Scheme不是一种流行的语言，也没有在工业环境下得到广泛使用，但它是本书的正确选择[1]。

本书的目的是介绍和解释一些编程思想。由于许多原因，相较于更流行的语言来说，用Scheme来阐述这些思想的示例代码更短、更简单。而且，有些想法几乎不可能用其他语言来展示。

除了Lisp家族的语言之外，其他语言需要大量的烦琐流程来表达简单的事情。使代码变得冗长的唯一原因是我们倾向于为计算对象使用冗长的描述性名称。

事实上，Scheme的语法非常简单——它只是自然解析树的表示，只需要最小的解析——这使得我们很容易编写处理程序文本的程序，如解释器、编译器和代数表达式操作器。

重要的是，Scheme是一种符合标准的语言，而不是一种规范性的语言。它并不试图阻止程序员做一些“愚蠢”的事情。这使得我们可以制作一些强大的游戏，比如动态地调节算术运算符的含义。如果我们使用的是限制性较强的语言，就无法做到这一点。

Scheme允许赋值，但更鼓励功能性编程。Scheme没有静态类型，但它有非常强大的动态类型，允许安全的动态存储分配和垃圾回收：用户程序不能创建指针或访问任意的内存位置。这并不是说我们认为静态类型不好，它们对于一大类程序错误（bug）的早期调试肯定是有用的。而类似Haskell类型的系统在思考策略方面也很有帮助。但是对于这本书来说，对静态类型的过度考量会抑制对潜在危险的灵活性策略的考虑。

此外，Scheme还提供了其他大多数语言所不具备的特殊功能，比如合一连续和动态绑定。这些特性使我们能够实现强大的机制，如在本地语言中实现非确定性的amb操作符（不需要第2层的解释）。

[1] 我们在附录B中对Scheme进行了简短介绍。