下载掌阅APP，畅读海量书库
立即打开
在1.1.8节，我们已经注意到，在用函数作为元素构造更复杂的函数时，这些函数不仅可以看作一组具体操作，也可以看作函数抽象。也就是说，相关函数的实现细节可以不论，某个特定的函数完全可以用另一个整体行为相同的函数取代。换句话说，我们可以做出这样的抽象，它分离了函数应该如何使用与其如何通过更基本的函数实现的细节。针对复合数据的类似概念称为 数据抽象 。数据抽象是一种方法学，它使我们能分离复合数据对象如何使用与其如何由更基本的数据对象构造起来的细节。
数据抽象的基本思想，就是在构造使用复合数据对象的程序时，设法使它们就像是在“抽象数据”上操作。也就是说，我们的程序使用数据的方式应该是：除了完成当前工作所必要的情况外，不对所用数据做任何额外的假设。与此同时，一种“具体”数据表示的定义也应该与程序中使用该数据的方法无关。在我们的系统里，这样两个部分之间的接口是一组函数，称为 选择函数 和 构造函数 ，它们在具体数据表示的基础上实现抽象的数据。为了展示这套技术，我们现在考虑怎样为操作有理数设计一集函数。
假定我们希望做有理数上的算术，希望能对它们做加、减、乘、除运算，以及比较两个有理数是否相等，等等。
作为开始，我们假定已经有了一种方法，可以从一个分子和一个分母构造出一个有理数。再进一步假定，如果有了一个有理数，我们有办法提取出（选取）它的分子和分母。现在再假定这些构造和选择的功能都可以作为函数使用：
●make_rat（ n , d ）返回一个有理数，其分子是整数 n ，分母是整数 d 。
●numer（ x ）返回有理数 x 的分子。
●denom（ x ）返回有理数 x 的分母。
在这里我们使用了一种可称为 按愿望思维 的强大的综合策略。现在我们还没说如何表达有理数，也没有说如何实现函数numer、denom和make_rat。即使这样，如果我们真的有了这三个函数，那么就可以根据下面的关系去做有理数的加减乘除和相等判断了：
我们可以把上述规则表达为如下的几个函数：
这样我们就有了各种有理数运算，它们都定义在选择函数numer、denom和构造函数make_rat的基础上。当然，这些基础还没有定义。我们现在需要的就是有某种方式，利用它可以把一个分子和一个分母粘结到一起，形成一个有理数。
序对
为了在具体层面上实现这种数据抽象，我们的JavaScript环境提供了一种称为 序对 的复合结构，该结构通过基本函数pair构造。函数pair取两个参数，返回一个包含这两个参数作为成分的复合数据对象。给了一个序对，我们可以用基本函数head和tail分别提取其中的两个部分。因此，我们可以如下面这样使用pair、head和tail：
请注意，一个序对也是一个数据对象，可以像基本数据对象一样命名或操作。进一步说，我们还可以用pair构造出其元素本身也是序对的序对，并继续这样做下去。
在2.2节我们将看到，这种组合序对的能力，意味着序对可以作为通用的基本构件，用于构造任意种类的复杂数据结构。由函数pair、head和tail实现的这种基本复合数据 ——序对 ——就是我们需要的唯一粘合剂。基于序对构造起来的数据对象称为 表结构 数据。
有理数的表示
序对为完成有理数系统提供了一种自然的方法，我们可以把一个有理数简单表示为两个整数（分子和分母）的序对，因此很容易实现make_rat、numer和denom如下 [1] ：
还有，为了能显示计算的结果，我们可以把有理数打印成先是分子，在一个斜线符之后再打印相应的分母。基本函数stringify能把任意的值（这里是数值）转换为字符串。JavaScript的+运算符也被重载了，它不但能应用于两个数，也能应用于两个字符串。对后一种情况，它将给出这两个字符串
拼接
而成的字符串
。
现在就可以试验我们的有理数函数了
：
从最后一个例子的显示可以看到，上面的有理数实现并没有把有理数约化到最简形式。我们很容易通过修改make_rat的方式实现这种功能。如果我们有了一个如1.2.5节中那样的gcd函数，它可以求出两个整数的最大公约数，现在就可以利用它，在构造序对之前把分子和分母约化到最简形式，然后再构造相应的序对：
现在我们就有：
结果正如所期。为了完成这一改动，我们只需修改构造函数make_rat，完全不必修改任何实现实际运算的函数（如add_rat和mul_rat）。
练习2.1 请声明make_rat的一个更好的版本，使之可以正确处理正数和负数。make_rat应该把有理数规范化，当有理数为正时使它的分子和分母都是正数；如果有理数为负，那么就应该只让分子为负。
在继续讨论复合数据和数据抽象的更多实例之前，让我们先考虑一下上述有理数实例表现出的几个问题。我们的有理数运算，都是基于有理数的构造函数make_rat和选择函数numer、denom定义的。一般而言，数据抽象的基本思想就是为每类数据对象确定一集基本操作，对这类数据对象的所有其他操作都基于这些基本操作表述，而且，此后凡是需要处理这类数据对象时，也只使用这些操作。
图2.1 有理数包中的数据抽象屏障
图2.1是对我们的有理数系统的结构的一种形象化描述。其中的水平线表示 抽象屏障 ，它们隔离了系统中的不同层次。在系统的每一层，这种屏障都分离了使用数据抽象的程序部分（上面）与实现数据抽象的程序部分（下面）。使用有理数的程序只通过有理数包提供给“公众使用”的那些函数（add_rat、sub_rat、mul_rat、div_rat和equal_rat）完成对有理数的各种操作；这些函数转而又完全基于构造函数和选择函数make_rat、numer和denom实现；进而，这三个函数又在序对的基础上实现。这里只要求通过pair、head和tail可以操作序对，序对如何实现的细节与有理数包的其余部分完全无关。从作用上看，每一层的函数定义了相应抽象屏障的接口，建立起不同层次之间的联系。
这种简单思想有许多优点。第一个优点是它使程序更容易维护和修改。任何比较复杂的数据结构都可以基于程序设计语言提供的基本数据结构，采用多种不同的方式表示。当然，表示方式的选择可能影响在其上操作的程序，这样，如果后来表示方式改变了，所有受影响的程序都需要随之改变。对大型程序而言，这种修改工作将非常耗时，代价高昂，除非我们在设计时就已经把依赖表示的成分限制到很少的一些程序模块上。
举例说，把有理数约化到最简形式的工作完全可以不在构造时做，而是在每次访问有理数的成分时再做。这样考虑将产生另一套不同的构造函数和选择函数：
这一实现与前面实现的不同之处就是何时计算gcd。如果在有理数的典型使用中，我们需要多次访问同一个有理数的分子和分母，那么最好是在构造有理数时计算gcd。如果情况不是这样，那么把gcd的计算推迟到访问时也许更好。但是，在任何情况下，当我们从一种表示转到另一种表示时，函数add_rat、sub_rat等都完全不需要修改。
把对具体表示方式的依赖限制到少数几个接口函数，不但对修改和维护程序有益，同样也有益于程序的设计。因为，采用这种做法，使我们能保留考虑不同实现方式的灵活性。继续前面的简单例子。假定我们现在正在设计一个有理数程序包，但是还无法决定究竟是在创建时执行gcd，还是应该把它推迟到选择的时候。数据抽象方法使我们能推迟做决策的时间，而且又不会阻碍系统其他部分的工作进展。
练习2.2 请考虑平面上线段的表示问题。一个线段可以用两个点来表示，一个是线段的始点，另一个是终点。请声明构造函数make_segment和选择函数start_segment、end_segment，它们基于点的概念定义线段的表示。进而，点可以表示为两个数的序对，这两个成分分别表示点的 x 坐标和 y 坐标。请据此进一步给出定义这种表示的构造函数make_point和选择函数x_point、y_point。最后，请基于所定义的构造函数和选择函数，声明一个函数midpoint_segment，它以一个线段为参数，返回线段的中点（也就是坐标值是两个端点的平均值的那个点）。为试验这些函数，你还需要有一种打印点的方法，例如：
练习2.3 请实现一种平面矩形的表示（提示：你可能希望借用练习2.2的结果）。基于你的构造函数和选择函数创建几个函数，计算给定矩形的周长和面积等。现在请再为矩形的实现定义另一种表示。你能否设计好你的系统，提供适当的抽象屏障，使同一个周长或者面积函数对两种不同的表示都能工作？
在2.1.1节实现有理数时，我们基于三个未明确说明的函数make_rat、numer和denom实现了有理数操作add_rat、sub_rat等。在那里，我们预想这些操作是基于一些数据对象（分子、分母、有理数）定义的，这些对象的行为完全由这三个函数刻画。
那么， 数据 究竟是什么意思呢？说它就是“由给定的构造函数和选择函数实现的东西”好像还不够。显然，并不是任意三个函数都适合作为有理数实现的基础。我们需要保证，如果从一对整数n和d构造出一个有理数x，那么，提取x的numer和denom并将它们相除，得到的结果应该与n除以d相同。换句话说，make_rat、numer和denom必须满足，对任意整数n和任意非零整数d，如果x是make_rat（n, d），那么：
事实上，这也就是为了成为有理数表示的合适基础，make_rat、numer和denom必须满足的全部条件。一般而言，我们可以认为数据是由一组选择函数和构造函数，以及使这些函数能成为一套合法表示必须满足的一组特定条件定义的
。
这种观点不仅适用于定义“高层”数据对象，例如有理数，同样也适用于低层对象。请考虑序对的概念，前面我们用它定义有理数，但从来都没有说过序对究竟是什么，只说所用的语言为操作序对提供了三个函数pair、head和tail。有关这三个操作，我们需要知道的全部东西就是：如果用pair把两个对象粘在一起，那么就可以借助head和tail提取出这两个对象。也就是说，这些操作满足条件是：对任何对象x和y，如果z是pair（x, y），那么head（z）就是x，而tail（z）就是y。我们确实说过这三个函数是我们的语言提供的基本函数。然而，任何能满足上述条件的三个函数都可以用作实现序对的基础。下面这个令人吃惊的事实能最好地说明这一点：我们完全可以不用任何数据结构，只用函数就实现序对。下面是有关的几个函数声明 [2] ：
函数的这种使用方式，恰好对应了我们有关数据应该是什么的直观认识。不管怎么说，如果被要求说明某种东西确实是序对的一种合法表示方式，我们只需要验证其中的几个函数满足前面提出的所有条件。
应该特别注意一个微妙之处：这里的pair（x, y）返回的值是一个函数——也就是那个内部定义的函数dispatch。该函数有一个参数，并能根据实际参数是0还是1分别返回x或y。与此对应，head（z）定义为把z应用于0，这样，如果z是由pair（x, y）返回的函数，把z应用于0就会产生x，这样就证明了head（pair（x, y））产生x，恰如我们所需。类似的，tail（pair（x, y））将pair（x, y）生成的函数应用于1而得到y。因此，序对的这一函数式实现确实是一个合法实现。如果只通过pair、head和tail访问序对，我们完全无法区分这一实现与使用“真正的”数据结构的实现。
上面展示了序对的一种函数式表示，但这并不意味着我们用的语言就是这样做的（一种高效的序对实现可能基于JavaScript基本的 向量 数据结构），而只是说确实可以这样做。这一函数式表示虽然有些隐晦，但它确实是序对的一种完全合格的表示，因为它满足了序对需要满足的所有条件。这一实例也说明，把函数作为对象去操作的能力，自动为我们提供了一种表示复合数据的能力。这些现在看起来好像只是好玩，但实际上，数据的函数式表示也在我们的程序设计宝库里扮演着核心的角色。这种风格的程序设计通常称为 消息传递 。在第3章里讨论模型和模拟时，我们将用它作为一种基本工具。
练习2.4 下面是序对的另一种函数式表示。请针对这种表示方式，验证对任意的x和y，head（pair（x, y））都将产生x。
对应的tail应该如何定义？（提示：在验证这一表示确实能行时，可以利用1.1.5节介绍的代换模型。）
练习2.5 请证明，我们可以只用整数和算术运算，用乘积2 a ·3 b 对应的整数表示非负整数 a 和 b 的序对。请给出对应的函数pair、head和tail的声明。
练习2.6 如果觉得序对可以只用函数表示还不够令人震惊，那么请考虑，在一个可以对函数做各种操作的语言里，我们完全可以没有数（至少在只考虑非负整数的情况下），以下面的方式实现0和加一操作：
这一表示形式被称为Church 计数 ，这个名字来源于其发明人——逻辑学家Alonzo Church。λ演算也是Church的发明。
请直接声明one和two（不用zero和add_1）。（提示：请利用代换去求值add_1（zero）。）请给出加法函数+的一个直接声明（不通过反复应用add_1）。
Alyssa P.Hacker正在设计一个帮助人们求解工程问题的系统。她希望这个系统提供的一个特征是能操作不精确的量（例如用物理设备测量的参数），这种量具有已知的精度，所以，对这种近似量做计算，得到的结果也应该是已知精度的数值。
电子工程师可能用Alyssa的系统计算一些电子的量。有时他们必须使用下面的公式，从两个电阻值 R 1 和 R 2 计算它们并联的等价电阻值 R p ：
在这种情况里，已知的电阻值通常是电阻生产厂商给出的带误差保证的值。例如，你可能买到一支标明“6.8欧姆误差10%”的电阻，这时我们只能确定，该电阻的阻值在6.8-0.68=6.12和6.8+0.68=7.48欧姆之间。这样，如果把一支6.8欧姆误差10%的电阻与另一支4.7欧姆误差5%的电阻并联，这一组合的电阻值可以在大约2.58欧姆（如果两支电阻都具有最小值）和2.97欧姆（如果两支电阻都具有最大值）之间。
Alyssa的想法是实现一套“区间算术”，也就是可以用于组合“区间”（一些对象，用不精确值的可能范围表示）的一组算术运算。两个区间的加、减、乘、除的结果仍是一个区间，表示计算结果的可能范围。
Alyssa假设了一种称为“区间”的抽象对象，这种对象有两个端点，一个下界和一个上界。她还假定，给了一个区间的两个端点，就可以用数据构造函数make_interval构造出相应的区间。Alyssa先写了一个做区间加法的函数，她推断说，和的最小值应该是两个区间的下界之和，其最大值应该是两个区间的上界之和：
Alyssa还找出了两个这种区间的乘积的最小和最大值，用它们就能做出两个区间的乘积区间（math_min和math_max是求任意多个参数中的最小值和最大值的基本函数）。
为了做两个区间的除法，Alyssa用第一个区间乘以第二个区间的倒数。请注意，倒数区间的两个界限分别是原来区间的上界的倒数和下界的倒数：
练习2.7 Alyssa的程序还是不够完整，因为她还没有明确说明区间抽象的实现。这里是区间构造函数的声明：
请给出选择函数upper_bound和lower_bound的声明，完成这个实现。
练习2.8 请通过类似于Alyssa的推理，说明应该怎样计算两个区间的差。请声明相应的减法函数sub_interval。
练习2.9 区间的 宽度 是其上界和下界之差的一半。区间宽度是有关区间描述的值的非精确性的一种度量。对某些算术运算，两个区间的组合结果的宽度是参数区间宽度的函数，而对其他运算，组合区间的宽度不是参数区间宽度的函数。请证明，两个区间的和（与差）的宽度是被加（或减）区间的宽度的函数。举例说明，对乘法和除法，情况并非如此。
练习2.10 Ben Bitdiddle是一个专业程序员，他看了Alyssa工作后评论说，除以一个横跨0的区间的意义不清楚。请修改Alyssa的代码，检查这种情况并在发现时报错。
练习2.11 在看了这些东西之后，Ben又说出了下面这段有些神秘的话：“通过监测区间的端点，有可能把mul_interval分解为9种情况，其中只有一种情况需要做两次乘法”。请根据Ben的建议重写这个函数。
排除了自己程序里的错误后，Alyssa给一个潜在用户演示自己的程序。但那个用户却说她的程序解决的问题根本不对。他希望能有一个程序，可用于处理那种用一个中间值和一个附加误差的形式表示的数，也就是说，希望程序能处理3.5±0.15而不是[3.35, 3.65]。Alyssa回到自己的办公桌解决了这个问题。她另外提供了一套构造函数和选择函数：
不幸的是，Alyssa的大多数用户是工程师，现实中的工程师经常遇到只有很小的非精确性的测量值，而且常以区间宽度对区间中点的比值作为度量值。工程师常采用基于部件参数的百分数误差描述部件，就像前面说的电阻值的描述方式。
练习2.12 请声明一个构造函数make_center_percent，它以一个中心点和一个百分比为参数，产生所需的区间。你还需要声明一个选择函数percent，通过它可以得到给定区间的百分数误差，选择函数center与前面一样。
练习2.13 请证明，在误差为很小的百分值的情况下，存在一个简单公式，利用它可以从两个被乘区间的误差算出乘积的百分数误差。你可以假定所有的数为正，以简化问题。
经过相当多的工作后，Alyssa P.Hacker发布了她的最后系统。几年之后，在她已经忘记了这个系统之后，接到一个愤怒的用户Lem E.Tweakit发疯似的电话。看来Lem注意到并联电阻的公式可以写成两个代数上等价的公式：
和
他写了两个程序，以不同的方式计算并联电阻值：
Lem抱怨说，Alyssa的程序对两种不同计算方法给出不同的值。这确实是很严重的问题。
练习2.14 请确认Lem说的对。请用各种不同的算术表达式检查这个系统的行为。请构造两个区间 A 和 B ，并用它们计算表达式 A / A 和 A / B 。如果所用区间的宽度相对于中心值是很小的百分数，你可能会得到更多认识。请检查对中心-百分比形式（见练习2.12）进行计算的结果。
练习2.15 另一用户Eva Lu Ator也注意到了根据等价的不同代数表达式算出的区间的差异。她说，如果把公式写成一种形式，其中表示具有非精确值的名字不重复出现，那么Alyssa的系统产生出的区间的界限会更紧一些。她还说，正因为此，在计算并联电阻时，par2是比par1“更好的”程序。她说得对吗？
练习2.16 请给出一个一般性的解释：为什么等价的代数表达式可能导致不同计算结果？你能设计出一个区间算术包，使之没有这种缺陷吗？或者这件事情根本不可能做到？（警告：这个问题非常难。）