第 2 章

用数据构建抽象

我们在第 1 章中集中讨论了计算过程以及过程在程序设计中的作用。我们看到了如何使用基本数据（数）和基本操作（算术运算），如何通过组合、条件表达式和参数的使用将过程组合起来形成复合过程，以及如何通过使用 define 来抽象过程。我们看到，一个过程可以被视为一个过程局部演化的模式，我们对过程中所体现的一些常见过程模式进行了分类、推理和简单的算法分析。我们还看到，高阶过程增强了我们语言的能力，使我们能够操作一般的计算方法，并以此来推理。这就是程序设计的精髓所在。

在本章中，我们将研究更复杂的数据。第 1 章中的所有过程都作用于简单的数值数据，而简单数据对于许多我们希望用计算来解决的问题来说是不够的。程序通常被设计用于模拟复杂现象，在更多情况下，人们必须构造具有多个部分的计算对象，以模拟具有多个方面的现实世界现象。因此，如果说第 1 章的重点是通过组合过程来形成复合过程从而构建抽象，那么在本章中，我们将转向任何程序设计语言的另一个关键方面：它通过组合数据对象来形成复合数据，以提供构建抽象的手段。

我们为什么要在程序设计语言中引入复合数据？原因与引入复合过程相同：提升我们在设计程序时所能到达的概念层次，提高设计的模块性，并增强语言的表达能力。正如定义过程的能力使我们能够以比语言基本操作更高的概念层次来处理过程一样，构造复合数据对象的能力使我们能够以比语言基本数据对象更高的概念层次来处理数据。

考虑设计一个执行有理数算术系统的任务。我们可以设想一个操作 add-rat，它接受两个有理数并产生它们的和。从简单数据的角度来看，一个有理数可以被看作两个整数：分子和分母。因此，我们可以设计一个程序，其中每个有理数由两个整数（分子和分母）表示，而 add-rat 由两个过程实现（一个产生和的分子，另一个产生和的分母）。但这会很笨拙，因为我们需要显式地跟踪哪些分子对应哪些分母。在一个要对许多有理数执行许多操作的系统中，这些簿记细节将使程序变得极其混乱，更不用说它们对我们大脑造成的负担了。更好的做法是，如果我们可以把分子和分母"粘合在一起"形成一个序对——一个复合数据对象——使我们的程序能够以一种与将有理数视为单一概念单元相一致的方式来操作它。

复合数据的使用也能使我们提高程序的模块性。如果我们可以将有理数直接作为独立的对象来操作，那么我们就可以将程序中处理有理数的部分与有理数如何表示为整数序对的细节分离开来。将程序中处理数据对象表示方式的部分与处理数据对象使用方式的部分隔离开来，这种通用技术是一种强大的设计方法论，称为数据抽象。我们将看到，数据抽象如何使程序的设计、维护和修改变得更加容易。

复合数据的使用能真正提高程序设计语言的表达能力。考虑形成"线性组合" ax + by 的想法。我们可能希望写一个过程，它接受 a、b、x 和 y 作为参数，并返回 ax + by 的值。如果参数是数，这没有问题，因为我们可以直接定义过程

(define (linear-combination a b x y) 
  (+ (* a x) (* b y)))

但假设我们关心的不仅仅是数。假设我们想用过程的方式表达这样的思想：只要加法与乘法已经定义，就可以形成线性组合——用于有理数、复数、多项式或其他任何东西。我们可以将此表示为如下形式的过程

(define (linear-combination a b x y)     
  (add (mul a x) (mul b y))) 

其中 add 和 mul 不是基本过程 + 和 *，而是更复杂的东西，它们将对传入的 a、b、x 和 y 参数执行适当的操作。关键在于，linear-combination 唯一需要知道 a、b、x 和 y 的就是，过程 add 和 mul 将执行适当的操作。从过程 linear-combination 的角度看，a、b、x 和 y 是什么并不重要，更无关紧要的是它们如何以更基本的数据来表示。这个例子也说明了为什么程序设计语言提供直接操作复合对象的能力至关重要：如果没有这一点，像 linear-combination 这样的过程就没有办法将它的参数传递给 add 和 mul，而不必了解它们的详细结构。¹ 我们将在本章开始时实现前面提到的有理数算术系统。这将为我们讨论复合数据和数据抽象提供背景。与复合过程一样，需要解决的主要问题是抽象作为应对复杂性的一种技术，我们将看到数据抽象如何使我们能够在程序的不同部分之间建立合适的抽象屏障。

我们将看到，形成复合数据的关键在于，程序设计语言应该提供某种"胶水"，使数据对象可以组合起来形成更复杂的数据对象。胶水的种类很多。事实上，我们将发现如何完全不使用任何特殊的"数据"操作，仅使用过程就能形成复合数据。这将进一步模糊"过程"和"数据"之间的区别——这种区别在第 1 章末尾就已经开始变得模糊了。我们还将探索一些表示序列和树的常用技术。处理复合数据的一个关键思想是闭包的概念——也就是说，我们用来组合数据对象的胶水应该不仅能组合基本数据对象，还要能组合复合数据对象。另一个关键思想是，复合数据对象可以作为常规接口，以混合搭配的方式组合程序模块。我们通过展示一个利用闭包的简单图形语言来说明这些思想。

然后我们将通过引入符号表达式来增强语言的表示能力——这些数据的基本部分可以是任意符号而不仅是数。我们探索表示对象集合的各种替代方案。我们将发现，正如一个给定的数值函数可以通过许多不同的计算过程来计算，一个给定的数据结构也可以用许多不同的方式以更简单的对象来表示，而表示方式的选择会对操纵这些数据的过程的时间和空间需求产生显著影响。我们将在符号求导、集合的表示以及信息编码的上下文中研究这些思想。

接下来，我们将讨论处理在程序的不同部分可能有不同表示方式的数据的问题。这导致需要实现通用型操作，它必须能处理许多不同类型的数据。在有通用型操作的情况下保持模块性，需要比单纯数据抽象所能建立的更强大的抽象屏障。特别地，我们引入了数据导向的程序设计作为一项技术，它允许单独的数据表示被独立设计，然后增量地（即不修改现有代码）组合在一起。为了说明这种方法在系统设计中的威力，我们在章末将所学内容应用于实现一个对多项式进行符号算术的包，其中多项式的系数可以是整数、有理数、复数甚至其他多项式。