第2章
构造数据抽象

现在我们到了数学抽象中具决定性的一步：让我们忘记这些符号代表的事物……[数学家]不需要止步于此，有许多操作可以用于这些符号，完全不关心它们代表什么。

——Hermann Weyl（赫尔曼·外尔），《思维的数学方式》

我们在第1章关注的是计算过程以及函数在程序的设计中扮演的角色。我们看到了怎样使用基本数据（数）和基本操作（算术运算）；怎样通过复合、条件和使用参数组合起一些函数，构造复合函数；怎样用函数声明完成计算过程的抽象。我们也看到，函数可以看作一种计算过程的局部演化的模式，可以对函数蕴涵的计算过程的一些常见模式做分类、推理和简单的算法分析。我们还看到了高阶函数能如何提升我们语言的威力，使我们能操控通用的计算方法，并对它们做各种推理。这些都是程序设计中最基本的东西。

在这一章里，我们准备考察一些更复杂的数据。在第1章里，所有函数操作的都是简单的数值数据，而对于我们希望用计算处理的许多问题，只有这样的简单数据是不够的。存在很多有代表性的程序，其设计就是为了模拟复杂的现象，为此经常需要构造一些计算对象，这些对象通常都是由一些部分组成，用于模拟真实世界里的那些具有多重特征的现象。这样，与我们在第1章里所做的事情（把一些函数组合起来形成复合函数，通过这种方法构造抽象）对应，本章将转到每个程序设计语言都包含的另一关键方面，讨论它们提供的把数据对象组合起来形成 复合数据 ，进而构造抽象的方法。

我们为什么希望程序设计语言提供复合数据呢？个中缘由恰如需要复合函数，也是为了提升我们设计程序时可能处于的概念层次，提高我们的设计的模块性，增强我们语言的表达能力。声明函数的能力，使我们有可能站在比语言提供的基本操作更高的概念层次上处理计算过程。与之类似，构造复合数据的能力，也将使我们有可能站在比语言提供的基本数据对象更高的概念层次上，处理与数据有关的问题。

现在考虑设计一个系统，我们希望它能做有理数算术。我们可以设想一个运算add_rat，它以两个有理数为参数，产生它们的和。基于基本数据，一个有理数可以看作两个整数，一个分子和一个分母。这样，我们可以设计一个程序，其中的每个有理数用两个整数表示，一个作为分子，另一个作为分母。相应的add_rat用两个函数实现，一个产生和数的分子，另一个产生和数的分母。然而，这样做下去一定会非常难受，因为我们必须始终清晰地记住哪个分子对应哪个分母。在需要对许多有理数执行大量运算的系统里，这种记录细节的工作将严重搅乱我们的程序，而这些细节又与我们心中真正想做的事情没什么关系。如果能把一个分子和一个分母“粘在一起”，形成一个对偶——一个 复合数据对象 ——我们的程序就能以统一的方式，把一个有理数作为一个概念单位来操作。

使用复合数据还能使我们进一步提高程序的模块性。如果我们能把有理数当作对象，直接去操作它们，就有可能把处理有理数的那些程序部分，与有理数如何表示的细节（可能是表示为一对整数）相互隔离。分离程序中处理数据对象表示的部分与处理数据对象使用的部分是一种通用技术，也是一种威力强大的设计方法学，称为 数据抽象 。下面我们将会看到，数据抽象技术能如何使程序更容易设计、维护和修改。

复合对象的使用能带来程序设计语言的表达能力的真正提升。考虑构造“线性组合” ax + by 的思想。我们可能想到写一个函数，让它接受 a 、 b 、 x 和 y 作为参数并返回 ax + by 的值。如果参数是数值，这样做没有任何困难，我们立刻就能给出下面的函数声明：

但是，假如我们关心的不仅仅是数，假如在写这个函数时，我们希望的是表述基于加法和乘法构成线性组合的计算过程，其中的加法和乘法可能定义在有理数、复数、多项式或其他什么东西上，我们可以将其表述为下面形式的函数：

其中的add和mul不是基本函数+和*，而是某种更复杂的东西，对我们通过参数a、b、x和y送去的任何类别的数据，它们都能执行适当的操作。这里的关键是，对于a、b、x和y，linear_combination需要知道的所有东西就是函数add和mul总能执行合适的操作。从函数linear_combination的角度看，a、b、x和y究竟是什么其实并不重要，至于它们如何基于更基本的数据表示，那就更无关紧要了。这个例子也说明了为什么程序设计语言提供直接操作复合对象的能力如此重要。因为，如果没有这种能力，我们就没办法让类似linear_combination的函数将其参数传给add和mul，而不必知道这些参数的细节结构 。

在本章开始，我们说要实现一个有理数算术系统，如同上面所说的那样。这一工作也将作为本章后面部分讨论复合数据和数据抽象的基础。与复合函数的情况类似，在这里需要考虑的主要问题，同样是把抽象作为一种克服复杂性的技术。我们将会看到，数据抽象如何使我们能在程序的不同部分之间构筑起适当的 数据屏蔽 。

我们还会看到，为了构造复合数据，关键就在于程序设计语言应该提供某些种类的“黏合剂”，它们能把一些数据对象组合起来，形成更复杂的数据对象。可能存在许多不同种类的黏合剂。进而，我们还会发现可以如何不用任何特殊的“数据”操作，而只用函数，就能构造所需的复合数据。这种情况进一步模糊了“函数”和“数据”的区分。实际上，在第1章的最后，这一区分已经开始变得不那么清晰了。我们还要探索一些表示序列和树的常用技术。处理复合数据的一个关键思想是 闭包 的概念——也就是说，用于组合数据对象的黏合剂不但能用于组合基本数据对象，同样能用于组合复合数据对象。另一关键思想是，复合数据对象能作为 约定的接口 ，使我们可以采用 混合与匹配 的方式组合起多个程序模块。我们将给出一个利用了闭包概念的简单图形语言，阐释这方面的一些思想。

再后，我们还要通过对 符号表达式 的介绍，进一步扩大语言的表达能力。符号表达式数据的基本部分可以是任意的符号，而不仅仅是数。我们将探索表示对象集合的几种不同方法，由这项工作中可以看到，就像一个特定的数学函数可以通过许多不同的计算过程来计算一样，一种特定的数据结构，也可以通过许多不同方式表示为简单对象的组合。而且，表示的选择，有可能对操作这些数据的计算过程的时间与空间需求造成重大影响。我们将在符号微分、集合表示和信息编码的语境中研究这些思想。

作为下一个问题，我们要考虑在一个程序的不同部分，数据可能采用不同的表示。这种情况引出了实现 通用型操作 的需要，它们必须能处理多种不同类型的数据。与只有简单数据抽象的情况相比，要想在包含通用型操作的情况下维持模块性，就需要更强大的抽象屏蔽。特别地，我们要介绍 数据导向的程序设计 。这种技术使我们能独立设计每一种数据表示，而后通过添加的方式把它们组合到系统里（也就是说，不做任何修改）。作为本章的结束，我们将应用前面学过的东西实现一个多项式符号算术的程序包，展示上述系统设计方法的威力。在这里，多项式的系数可以是整数、有理数、复数，甚至还可以是其他多项式。 g0v3UDrEod6DZBXbIBYiqkCFVevnuti1SarsNQUcqnnY1mMipdJw1Q3vQFRjuW9L