《构造数据抽象》PPT课件

构造数据抽象,到目前为止，我们操作的都是简单的数值数据，而对我们希望处理的许多问题而言，这种简单数据还不够。许多程序在设计时就是为了模拟复杂的对象，因此他们就常常需要构造起一些计算对象。与我们在前面所做的事情一样，我们将重点转到各种程序设计语言的另一关键方面：讨论他们所提供的，将数据对象组合起来，形成复合数据的方式，并进一步去考查更复杂的数据。同样的我们还将要看到，与过程抽象相对应的，另一种强有力的设计方法学数据抽象,构造数据抽象,数据抽象是一种方法学，它使我们能够将一个复合数据对象的使用，与该数据对象怎样由更基本的数据对象构造起来的细节隔离开来。其基本思想，就是设法构造出一些使用复合对象的程序，使它们就像是在“抽象数据”上操作一样。也就是说，我们的程序中使用数据的方式应该是这样的：除了完成当前工作所必要的东西之外，它们不对所用数据做任何多余的假设。与此同时，一种“具体”数据表示的定义，也应该与程序中使用数据的方式无关。我们利用一组称为选择函数和构造函数的过程作为这两个部分之间的界面。,构造数据抽象,实例研究：有理数的算术运算我们希望能做有理数的加减乘除，比较两个有理数是否相等。我们假定已经有了一种从分子和分母构造有理数的方法。进一步假定，如果有了一个有理数，我们有一种方法取得它的分子和分母。现在再假定有关的构造函数和选择函数都可以做为过程使用：(make-rat)返回一个有理数，其分子是整数，分母是整数(numer)返回有理数的分子(denom)返回有理数的分母这里使用一种称为按愿望思维的策略。现在我们还没有说有理数将如何表示，也没有说过程make-rat，numer和denom应如何实现。利用这三个过程我们就可以实现有理数的运算了,构造数据抽象,有理数运算过程的实现：加法过程：(define(add-ratxy)(make-rat(+(*(numerx)(denomy)(*(numery)(denomx)(*(denomx)(denomy)减法过程：(define(sub-ratxy)(make-rat(-(*(numerx)(denomy)(*(numery)(denomx)(*(denomx)(denomy),构造数据抽象,乘法过程：(define(mul-ratxy)(make-rat(*(numerx)(numery)(*(denomx)(denomy)除法过程：(define(div-ratxy)(make-rat(*(numerx)(denomy)(*(denomx)(numery)相等判断过程：(define(equal-rat?xy)(=(*(numerx)(denomy)(*(numery)(denomx),构造数据抽象,有理数的表示：我们已经定义了在过程make-rat，numer和denom基础上的各种有理数的运算过程，而这些基础还没有定义。现在需要某种方式，将一个分子和一个分母粘接起来，构成一个有理数。在实现有理数之前我们先来看看我们所用的语言提供的一种称为序对的复合数据。序对为完成这里的有理数系统提供了一种自然的方式，我们可以将有理数简单的表示为两个整数（分子和分母）的序对。,构造数据抽象,序对：同样我们只关心序对选择函数和构造函数的形式，而实际过程已由解释器实现了(cons),过程cons取两个参数，返回一个包含这两个参数作为其成分的复合数据对象(car)，其序对中的第一个参数(cdr)，其序对中的第二个参数注意一个序对也是一个数据对象，可以像基本数据对象一样给它一个名字且操作它。还可用cons构造其元素本身就是序对的序对，例如：(definex(cons12)(definey(cons34)(definez(consxy)(car(carz)1(car(cdrz)2,构造数据抽象,基于序对的有理数的表示：(define(make-ratnd)(consnd)(define(numerx)(carx)(define(denomx)(cdrx)为了显示计算结果我们再定义一个打印函数，它以一个有理数作为输入并把它打印出来。(define(print-ratx)(newline)(display(numerx)(display/)(display(denomx)这里我们用到了两个scheme的基本内置过程display和newline。Display为打印数据的基本过程，newline为随后的打印开始一个新行。,构造数据抽象,(defineone-half(make-rat12)(print-ratone-half)(defineone-third(make-rat13)(print-rat(add-ratone-halfone-third)(print-rat(mul-ratone-halfone-third)(print-rat(add-ratone-thirdone-third)看看上面的过程都会打印出什么？从打印结果你们发现了什么问题？能否改进？,构造数据抽象,抽象屏障：在继续讨论之前，让我们首先回顾一下有理数系统的结构：问题域中的有理数作为分子和分母的有理数作为序对的有理数当然序对也需要实现,使用有理数的程序,add-ratsub-rat,conscarcdr,make-ratnumberdenom,构造数据抽象,其中的水平线表示抽象屏障，它隔离了系统的不同层次，它把使用数据的程序和实现数据的程序分开，使得一层中的过程的实现与其他层的过程的实现完全无关。从作用上看，每一层中的过程构成了所定义的抽象屏障的界面，联系起系统中的不同层次。这种简单思想有许多优点：这种方法使程序很容易维护和修改有助于程序的设计，使我们能保留考虑不同实现方式的灵活性，使我们能推迟决策的时间，而又不会阻碍系统其他部分的工作进展。你能给出几种不同的有理数表示？它们各有什么优缺点？,构造数据抽象,数据意味着什么前面我们看到在抽象层面上数据可以描述为一组选择函数和构造函数，但是说它就是“由给定的选择函数和构造函数所实现的东西”还是不够的。显然，并不是任意的三个过程都适合作为有理数实现的基础。这里我们还需要保证，如果从整数n和d构造出一个有理数x，那么抽取出的x的number和denom并将他们相除，得到的结果应该与n除以d相同。也就是说这些基本过程的选择是带有约束的。一般而言，我们总可以将数据定义为一组适当的选择函数和构造函数，以及为使这些过程成为一套合法表示，它们就必须满足的一组特定条件。从上面我们可以得出一个结论：数据其实就是一组定义良好的过程。确实，考虑序对，我们完全可以不用任何数据结构，只用过程实现它。,构造数据抽象,序对的过程实现：(define(consxy)(define(dispatchm)(cond(=m0)x)(=m1)y)(else(errorArgumentnot0or1-CONSm)dispatch)(define(carz)(z0)(define(cdrz)(z1)这确实与我们有关数据应该是什么的直观认识大相径庭。这一实例说明可以将过程作为对象去操作，因此就自动地为我们提供了一种表示复合数据的能力。这些东西现在看起来好像只是很好玩，但实际上，数据的过程性表示将在我们的程序设计宝库里扮演一种核心角色。有关的程序设计风格通常称为消息传递。,层次性数据和闭包性质,前面已经看到，序对为我们提供了一种用于构造复合数据的基本“粘接剂”，我们可以建立元素本身也是序对的序对，序对的这种能力称为cons的闭包性质。一般说，某种数据对象的操作满足闭包性质，就是说，通过它组合起数据对象得到的结果本身还可以通过同样的操作再进行组合。闭包性质是任何一种组合功能的威力的关键要素，它使我们能够建立起层次性的结构。,层次性数据和闭包性质,层次性结构的表示：图中展示的是序对的标准表示，其中的序对是通过(cons12)形成的。这种称为盒子和指针表示方式中，每个对象表示为一个指向盒子的指针。与基本对象相对应的盒子包含着该对象的表示。复合层次结构的表示：,层次性数据和闭包性质,序列的表示：我们可以用序对构造一种有用的数据结构序列，它是一批数据对象的一种有序汇集。采用序对表示序列有很多种方式，在这里我们采用一种标准的方式来表示。下面是对序列1，2，3，4的表示：(cons1(cons2(cons3(cons4nil)通过嵌套的cons形成的这样一个序对的序列称为一个表，scheme为方便表的构造，提供了一个基本操作list，如(list1234)。一般的：(list.)等价于：(cons(cons(cons.(consnil).),层次性数据和闭包性质,序对的打印：(cons12);(1.2)(cons(cons12)(cons34);(1.2)3.4)(cons1(cons2(cons3nil);(123),层次性数据和闭包性质,表的打印：(list1234);(1234)(defineone-through-four(list1234)one-through-four;:(1234)(carone-through-four);:1(cdrone-through-four);:(234)(car(cdrone-through-four);:2(cons10one-through-four);:(101234),层次性数据和闭包性质,表操作：利用序对将元素表示为表之后，我们就可以使用常规的程序设计技术，通过”向下cdr”表的方式完成对表的各种操作了。返回指定标号的元素操作：list-ref(define(list-refitemsn)(if(=n0)(caritems)(list-ref(cdritems)(-n1)(definesquares(list1491625);:(list-refsquares3)16注意：这里我们习惯令表元素的编号从0开始。,层次性数据和闭包性质,返回表的长度操作：length(define(lengthitems)(if(null?items)0(+1(length(cdritems)(defineodds(list1357)(lengthodds)4这里我们需要用到scheme提供的一个基本操作null?，用于检查参数是不是空表。上面的过程是一个递归的过程，空表的length为0，任一表的length等于其cdr的length加1.给出迭代的length过程？,层次性数据和闭包性质,连接表操作：append(define(appendlist1list2)(if(null?list1)list2(cons(carlist1)(append(cdrlist1)list2)(appendsquaresodds);:(appendoddssquares);:append也是一种递归方案，能否给出迭代形式？,层次性数据和闭包性质,对表的映射：例：对给定表的所有元素按给定因子做一次放缩(define(scale-listitemsfactor)(if(null?items)nil(cons(*(caritems)factor)(scale-list(cdritems)factor)(scale-list(list12345)10);:(1020304050)这里我们想抽象出这一具有一般性的想法，将其中公共模式表述为一个高阶过程，这一高阶过程称为map，它有一个过程参数和一个表参数，返回将这一过程应用于表中各个元素得到的结果形成的表。,层次性数据和闭包性质,对表的映射过程：map(define(mapprocitems)(if(null?items)nil(cons(proc(caritems)(mapproc(cdritems)(map(lambda(x)(*xx)(list1234)(14916)用map重新定义scale-list过程：(define(scale-listitemsfactor)(map(lambda(x)(*xfactor)items),层次性数据和闭包性质,层次性结构：(12)34)是通过(cons(list12)(list34)构造出来的，其结构如下：认识这种元素本身也是序列的序列的另一种方式，是把它们看作树。序列里的元素就是树的分支，而那些本身也是序列的元素就形成了树中的子树。如图：,层次性数据和闭包性质,树操作：统计叶子数目操作：count-leaves(define(count-leavesx)(cond(null?x)0)(not(pair?x)1)(else(+(count-leaves(carx)(count-leaves(cdrx)为了实现这一过程，我们需要一个判断参数是否为序对的函数，scheme提供了基本过程pair?,层次性数据和闭包性质,对树的映射：(define(scale-treetreefactor)(cond(null?tree)nil)(not(pair?tree)(*treefactor)(else(cons(scale-tree(cartree)factor)(scale-tree(cdrtree)factor)(scale-tree(list1(list2(list34)5)(list67)10);:(10(20(3040)50)(6070)该过程以一个数值因子和一颗叶子为数值的树作为参数，返回一颗具有同样形状的树。,层次性数据和闭包性质,下面我们利用前面介绍表的map过程重写如下：(define(scale-treetreefactor)(map(lambda(sub-tree)(if(pair?sub-tree)(scale-treesub-treefactor)(*sub-treefactor)tree)也已看到这里map过程的写法已经没有在用于处理表时那么自然了，究其原因是因为map过程并不具备处理层次结构的能力，这样我们在使用是就必须把相关处理写到其参数proc的过程里面。自然地，我们希望能有一个能处理这种层次结构的map过程，当然其肯定也包含了处理表结构的能力，应为树结构是一种比表更抽象的结构。,层次性数据和闭包性质,重写前面的map过程如下：(define(mapprocitems)(cond(null?items)nil)(pair?items)(cons(mapproc(caritems)(mapproc(cdritems)(else(procitems)请利用新定义的map过程重写scale-list和scale-tree,层次性数据和闭包性质,序列作为一种约定的界面：下面这个例子以一棵树为参数，计算出那些值为奇数的叶子的平方：(define(sum-odd-squarestree)(cond(null?tree)0)(not(pair?tree)(if(odd?tree)(squaretree)0)(else(+(sum-odd-squares(cartree)(sum-odd-squares(cdrtree)该过程的大致处理步骤如下：枚举出一棵树的树叶；过滤他们，选出其中的奇数；对选出的每个数求平方；再用+累积起得到的结果，从0开始。,层次性数据和闭包性质,这种过程可以很自然地用流过一些级联的处理步骤的信号的方式描述，其中的每个处理步骤实现程序方案中的一个部分，如图所示：我们从一个枚举器开始，它产生出由个给定的树的所有树叶组成“信号”。这一信号流过一个过滤器，所有不是奇数的数都被删除了。这样得到的信号又通过一个映射，这是一个“转换装置”，它将square过程应用于每个元素。这一映射的输出被馈入一个累积器，该装置用+将得到的所有元素组合起来，从0开始。,enumerate：treeleaves,filter：odd?,map：square,accumulate：+,0,层次性数据和闭包性质,序列操作：要组织好反映上面信号流的结构的程序，最关键的一点就是将注意力集中在处理过程中从一个步骤流向下一个步骤的“信号”。这些信号应该有稳定而灵活的结构，基于其上的基本操作可以组织好这些处理过程。表在这里就是一个良好的选择。基于表结构我们可以很好的实现信号流图中的过程如下：前面的map过程可以用来实现信号流图中的映射步骤：过滤一个序列，就是选出其中满足某个给定谓词的元素，实现如下：(define(filterpredicatesequence)(cond(null?sequence)nil)(predicate(carsequence)(cons(carsequence)(filterpredicate(cdrsequence)(else(filterpredicate(cdrsequence),层次性数据和闭包性质,累积工作可以实现如下：(define(accumulateopinitialsequence)(if(null?sequence)initial(op(carsequence)(accumulateopinitial(cdrsequence)剩下的就是枚举出需要处理的数据序列，对于上面的例子，需要枚举出一棵树的所有树叶，可实现如下：(define(enumerate-treetree)(cond(null?tree)nil)(not(pair?tree)(listtree)(else(append(enumerate-tree(cartree)(enumerate-tree(cdrtree),层次性数据和闭包性质,现在，我们就可以像上面的信号流图那些重新构造sum-odd-squares了。我们需要枚举一棵树的树叶序列，过滤它，只留下序列中的奇数，求每个元素的平方，而后加起来得到的结果：(define(sum-odd-squarestree)(accumulate+0(mapsquare(filterodd?(enumerate-treetree)将程序表示为一些针对序列的操作，这样做的价值就在于能帮助我们得到模块化的程序设计，也就是说，得到由一些比较独立的片段的组合构成的设计。而模块化结构是控制复杂性的一种威力强大的策略。在这里，用表实现的序列被作为一种方便的界面，我们可以利用这种界面去组合其各种处理模块，并将程序对数据结构的依赖性局限到不多的几个序列操作上。通过修改这些操作，就可以在序列的不同表示之间转换，并保持程序的整个设计不变。,符号数据,到目前为止，我们已经使用过的所有复合数据，最终都是从数值出发构造起来的。接下来，我们将要扩充所用语言的描述能力，引进将任意符号作为数据的能力。我们希望构造出表(ab)，当然这里不能用(listab)，因为这将构造出a和b的值的表，而不是其符号本身。为了能构造出这些符号，我们使用的语言里就需要有一种新元素，它具有引用数据对象的能力。在scheme里我们通过一个单引号来引用一个对象。,符号数据,现在我们可以通过单引号区分一个符号和他们的值了：(definea1)(defineb2)(listab);:(12)(listab);:(ab)(listab);:(a2)引号也可以用于复合对象：(car(abc);:a(cdr(abc);:(bc),符号数据,对符号的操作：为了能对符号进行各种操作，我们的语言提供了一个基本过程eq?，这个过程以两个符号作为参数，检查它们是否为同样的符号。我们利用eq?实现一个称为memq的有用过程，它以一个符号和一个表为参数。如果这个符号不包含在这个表里，就返回假；否则返回该表的由这个符号的第一次出现开始的那个子集：(define(memqitemx)(cond(null?x)false)(eq?item(carx)x)(else(memqitem(cdrx)(memqapple(pearbananaprune);:false(memqapple(x(applesauce)yapplepear);:(applepear),符号数据,解释器在求值下面各个表达式时将打印出什么？(listabc)(list(listgeorge)(cdr(x1x2)(y1y2)(cadr(x1x2)(y1y2)(pair?(car(ashortlist)(memqred(redshoes)(bluesocks)(memqred(redshoesbluesocks),符号数据,实例研究：符号求导我们希望实现一个过程，以一个代数表达式和一个变量作为参数，返回这个表达式相对于该变量的导数。如：参数为ax2+bx+c和x，它应该返回2ax+b。当然，一个强有力的符号求导系统的开发是很困难的，为了使有关讨论简单化，我们在这里考虑一个非常简单的符号求导程序，它处理的表达式都是由对于两个参数的加和乘运算构造起来的。这样其求导可以通过下面几条规则完成：,符号数据,为了能在一个过程中体现这些规则，我们用一下按愿望思维，就像在前面设计有理数的实现所做的那样。假设现在已经有了一种表示代数表达式的方式，那么我们需要判断该表达式是否为一个和式、乘式、常量、变量，还需要能提取出表达式的各个部分。也就是说我么在这里需要一组构造函数、选择函数和谓词作为我们求导程序的界面：(variable?e)e是变量吗？(same-variable?v1v2)v1和v2是统一变量吗？(sum?e)e是和式吗？(addende)e的被加数(augende)e的加数(make-suma1a2)构造a1与a2的和式(product?e)e是乘式吗？(multipliere)e的被乘数(multiplicande)e的乘数(make-productm1m2)构造m1与m2的乘式,符号数据,利用上面这些过程，以及判断表达式是否数值的基本过程number？，我们就可以将各种求导规则用下面的过程表达出来了：(define(derivexpvar)(cond(number?exp)0)(variable?exp)(if(same-variable?expvar)10)(sum?exp)(make-sum(deriv(addendexp)var)(deriv(augendexp)var),符号数据,(product?exp)(make-sum(make-product(multiplierexp)(deriv(multiplicandexp)var)(make-product(deriv(multiplierexp)var)(multiplicandexp)(else(errorunknownexpressiontype-DERIVexp)过程deriv包含了一个完整的求导算法。因为它是基于抽象数据表述的，因此，无论我们如何选择代数表达式的具体表示，只要设计了一组正确的选择函数和构造函数，这个过程都可以工作。,符号数据,代数表达式的表示：我们可以想出很多用表结构表示代数表达式的方法，一种特别直截了当的选择，是采用Lisp里面表示组合式的那种带括号的前缀形式：变量就是符号，他们可以用基本谓词symbol?判断：(define(variable?x)(symbol?x)两个变量相同就是表示它们的符号相互eq?：(define(same-variable?v1v2)(and(variable?v1)(variable?v2)(eq?v1v2)和式与乘式都构造为表：(define(make-suma1a2)(list+a1a2)(define(make-productm1m2)(list*m1m2)和式就是第一个元素为符号+的表：(define(sum?x)(and(pair?x)(eq?(carx)+),符号数据,被加数是表示和式的表里的第二个元素：(define(addends)(cadrs)加数是表示和式的表里的第三个元素：(define(augends)(caddrs)乘是就是第一个元素为符号*的表：(define(product?x)(and(pair?x)(eq?(carx)*)被乘数是表示乘式的表里的第二个元素：(define(multiplierp)(cadrp)乘数是表示乘式的表里的第三个元素：有了代数表达式的具体表示以后我们就能实际使用求导程序了：(define(multiplicandp)(caddrp);:(deriv(+x3)x);:(deriv(*xy)x);:(deriv(*(*xy)(+x3)x),符号数据,有了代数表达式的具体表示以后，我们就能实际使用求导程序了：(define(multiplicandp)(caddrp);:(+10)(deriv(+x3)x);:(+(*x0)(*1y)(deriv(*xy)x);:(deriv(*(*xy)(+x3)x);:(+(*(*xy)(+10)(*(+(*x0)(*1y)(+x3)我们可以看到程序产生的结果是对的，但是他们没有经过化简。当然，我们希望程序能够知道x*0=0,1*y=y以及0+y=y。我们可以想想在有理数中碰到的情形。同样我们可以通过修改选择函数和构造函数实现这一化简，完全不必修改deriv。,符号数据,新的make-sum过程，当两个求和对象都是数时，返回他们的和，当其中一个为零时，返回另外一个对象：(define(make-suma1a2)(cond(=number?a10)a2)(=number?a20)a1)(and(number?a1)(number?a2)(+a1a2)(else(list+a1a2)该过程用到了=number?，它检查某个表达式是否等于一个给定的数。(define(=number?expnum)(and(number?exp)(=expnum),符号数据,与make-sum类似，修改后的make-prouct过程，设法引进下面的规则：0与任何对象的乘积都是0，1与任何东西的乘积总是那个对象(define(make-productm1m2)(cond(or(=number?m10)(=number?m20)0)(=number?m11)m2)(=number?m21)m1)(and(number?m1)(number?m2)(*m1m2)(else(list*m1m2)下面使这一新版过程对前面三个例子的结果：;:1;:y;:(+(*xy)(*y(+x3)虽然大有改观，但第三个例子还是说明，这不足以满足我们认为的最简形式。思考这里所谓的最简形式的含义，它有没有统一的风格？,抽象数据的多重表示,抽象屏障是控制复杂性的强有力的工具。通过对数据对象基础表示的屏蔽，我们就可以将设计一个大程序的任务，分割为一组可以分别处理的较小任务。但是，这种类型的数据抽象还不够强大有力。从一个角度看，对于一个数据对象可能存在多种有用的表示方法，而且我们也可能希望所设计的系统能处理多种表示形式。例如：复数可以表示为两种等价的形式：直角坐标（实部和虚部）和极坐标（模和幅角）。有时采用直角坐标形式更合适，有时极坐标形势更方便。所以，我们可能希望一个系统能同时采用两种表示形式。而其中的过程可以对具有任意表示形式的复数工作。接下来我们就通过实现这一复数系统来展示抽象数据的多重表示技术。,抽象数据的多重表示,利用一个按愿望思维，我们希望有如下2个构造函数和4个选择函数：make-frome-real-imag:返回一个采用实部和虚部描述的复数；make-frome-mag-ang:返回一个采模和幅角描述的复数；real-part:以一个复数为参数，返回其实部；imag-part:以一个复数为参数，返回其虚部；magnitude:以一个复数为参数，返回它的模；angle：以一个复数为参数，返回其幅角；这些过程的性质是：(make-from-real-imag(real-partz)(imag-partz)(make-from-mag-ang(magnitudez)(anglez)产生出的复数都等于z。利用这些构造函数和现在函数，我们就可以实现复数的运算了。,抽象数据的多重表示,我们希望，加减法采用实部和虚部的方式描述，而乘除法采用模和幅角的方式描述：(define(add-complexz1z2)(make-from-real-imag(+(real-partz1)(real-partz2)(+(imag-partz1)(imag-partz2)(define(sub-complexz1z2)(make-from-real-imag(-(real-partz1)(real-partz2)(-(imag-partz1)(imag-partz2)(define(mul-complexz1z2)(make-from-mag-ang(*(magnitudez1)(magnitudez2)(+(anglez1)(anglez2)(define(div-complexz1z2)(make-from-mag-ang(/(magnitudez1)(magnitudez2)(-(anglez1)(anglez2),抽象数据的多重表示,为了完成这一复数包，我们必须选择一种表示方法，而且必须基于基本的数值和基本的表结构。有两种显而易见的方式完成这一工作：可以将复数按“直角坐标形式”表述为一个有序对（实部，虚部），或者“极坐标形式”表示为序对（模，幅角）。假设现在已经设计出了这两种复数系统的具体表示形式。基于直角坐标的表示形式：(define(real-partz)(carz)(define(imag-partz)(cdrz)(define(magnitudez)(sqrt(+(square(real-partz)(square(imag-partz)(define(anglez)(atan(imag-partz)(real-partz)(define(make-from-real-imagxy)(consxy)(define(make-from-mag-angra)(cons(*r(cosa)(*r(sina)上面用到了一个反正切函数atan，它取两个参数y和x，返回正切是y/x的角度。参数的符号决定角度所在的象限,抽象数据的多重表示,基于极坐标的表示形式：(define(real-partz)(*(magnitudez)(cos(anglez)(define(imag-partz)(*(magnitudez)(sin(anglez)(define(magnitudez)(carz)(define(anglez)(cdrz)(define(make-from-real-imagxy)(cons(sqrt(+(squarex)(squarey)(atanyx)(define(make-from-mag-angra)(consra)数据抽象的规则保证了复数的加减乘除运算的同一套实现对这两种表示都能正常工作。,抽象数据的多重表示,究竟应该选择哪一种表示方式？我们处在一个尴尬的境地了，因为这两表示形式同样的有用，我们希望同时获得这两种表示形式的优点。能不能在同一个系统里包含两种不同的表示形式？答案是能，但我们需要一种方式，将极坐标形式的数据和直角坐标形式的数据区分。完成这种区分的一种方式，就是在每个复数里包含一个类型标志部分用符号rectangular或者polar。此后如果我们需要操作一个复数，借助于这个标志就可以确定应该使用的选择函数了。为了能对带标志数据进行各种操作，我们将假定有过程type-tag和contents,它们分别从数据对象中提取出类型标志和实际内容。还要假定有一个过程它以标志和实际内容为参数，生成出一个带标志的数据对象。实现这些的直接方式就是采用普通表结构：(define(attach-tagtype-tagcontents)(constype-tagcontents)(define(type-tagdatum)(if(pair?datum)(cardatum)(errorBadtaggeddatum-TYPE-TAGdatum),抽象数据的多重表示,(define(contentsdatum)(if(pair?datum)(cdrdatum)(errorBadtaggeddatum-CONTENTSdatum)利用这些过程，我们就可以定义出谓词rectangular?和polar?,他们分别辨识直角坐标表示和极坐标表示的复数：(define(rectangular?z)(eq?(type-tagz)rectangular)(define(polar?z)(eq?(type-tagz)polar)有了类型标志之后，我们可以修改前面的代码，使两种不同表示能够共存于同一个系统中了。在不同的表示形式中，构造一个复数时，总为它加上对应的标志。此外还必须保证所用的过程名不冲突。这样应为过程名也加上相应的后缀。经过修改后的两种表示形式如下：,抽象数据的多重表示,修改后的直角坐标表示：(define(real-part-rectangularz)(carz)(define(imag-part-rectangularz)(cdrz)(define(magnitude-rectangularz)(sqrt(+(square(real-part-rectangularz)(square(imag-part-rectangularz)(define(angle-rectangularz)(atan(imag-part-rectangularz)(real-part-rectangularz)(define(make-from-real-imag-rectangularxy)(attach-tagrectangular(consxy)(define(make-from-mag-ang-rectangularra)(attach-tagrectangular(cons(*r(cosa)(*r(sina),抽象数据的多重表示,修改后的极坐标表示：(define(real-part-polarz)(*(magnitude-polarz)(cos(angle-polarz)(define(imag-part-polarz)(*(magnitude-polarz)(sin(angle-polarz)(define(magnitude-polarz)(carz)(define(angle-polarz)(cdrz)(define(make-from-real-imag-polarxy)(attach-tagpolar(cons(sqrt(+(squarex)(squarey)(atanyx)(define(make-from-mag-ang-polarra)(attach-tagpolar(consra),抽象数据的多重表示,基于上面的两种表示我们需要实现通用型函数，它们首先检查参数的标志，而后去调用处理该类数据的适当过程。(define(real-partz)(cond(rectangular?z)(real-part-rectangular(contentsz)(polar?z)(real-part-polar(contentsz)(else(errorUnknowntype-REAL-PARTz)(define(imag-partz)(cond(rectangular?z)(imag-part-rectangular(contentsz)(polar?z)(imag-part-polar(contentsz)(else(errorUnknowntype-IMAG-PARTz),抽象数据的多重表示,(define(magnitudez)(cond(rectangular?z)(magnitude-rectangular(contentsz)(polar?z)(magnitude-polar(contentsz)(else(errorUnknowntype-MAGNITUDEz)(define(anglez)(cond(rectangular?z)(angle-rectangular(contentsz)(polar?z)(angle-polar(contentsz)(else(errorUnknowntype-ANGLEz)我们可以看到前面的复数加减乘除的运算仍然无须改动。,抽象数据的多重表示,最后，我们还需要确定采用那种构造复数的方式。一种合理的选择是：在手头有实部和虚部时采用直角坐标表示，有模和幅角时采用极坐标表示：(define(make-from-real-imagxy)(make-from-real-imag-rectangularxy)(define(make-from-mag-angra)(make-from-mag-ang-polarra),抽象数据的多重表示,这样回过头来看我们所定义的过程，我们用一种非常自然的鉴别方式，成功的把复数的两种不同表示形式包含到同一个复数包中了。这样得到的系统具有如下图所示的结构：使用复数的程序复数算术包直角坐标表示极坐标表示,add-complexsub-complexmul-complexdiv-complex,real-partimag-partMagnitudeangle,抽象数据的多重表示,数据导向的程序设计和可加性：基于类型的分派，在系统设计中是一种获得模块性的强有力的策略。而另一方面，同前面那样实现的分派有两个显著的弱点。一是，其中的这些通用型界面过必须知道所有的不同表示，如果现在希望增加另一种表示，我们就必须将这一新表示方法标识为一种新类型，而且要在每个通用界面过程里增加一个句子，检查这一新类型，并对这种表示形式使用适当的选择函数。还有一个弱点就是，即使这些独立的表示形式可以分别设计，我们也必须保证在整个系统里不存在两个名字相同的过程。由此带来的问题是，这种实现通用型界面的技术不具有可加性。因为每次增加一种新表示时，实现通用选择函数的人都必须修改它们的过程，而那些做独立表示界面的人也必须修改其代码，以避免名字冲突问题。很多时候这种做法会带来极大的不变，而且还很容易引进错误。接下来我们介绍将系统进一步模块化的方法，通过使用一种称为数据导向的程序设计的编程技术。,抽象数据的多重表示,事实上，我们正是在处理一个二维表格，其中的一个维上包含着所有的可能操作，另一个维就是所有的可能类型。如图：数据导向的程序设计就是一种使程序能直接利用这种表格工作的程序设计技术。它用操作名和参数类型的组合到表格中查找，以便找出应该调用的适当过程，并将这一过程应用于参数的内容。这样把一种新的表示包加入系统里，我们就不需要修改任何现存的过程，而只要在这个表格里添加一些新的项目即可。,抽象数据的多重表示,为了实现这一计划，现在假定有两个过程put和get，用于处理这种操作类型表格：(put)：将项加入表格中，以和作为这个表项的索引(get)：在表中查找和对应的项，如果找到就返回找到的项，否则就返回假。下面我们要说明，这种数据导向的程序设计可以如何用于复数系统。我们在定义完复数的表示的程序包后，要通过向表格中加入一些项的方式，告诉系统如何去操作直角坐标形式表示的数，这样就建立起了与系统其它部分的界面。我们通过安装的方式向表中加入我们要提供出来的过程。,抽象数据的多重表示,直角坐标表示包的安装过程：(define(install-rectangular-package);internalprocedures(define(real-partz)(carz)(define(imag-partz)(cdrz)(define(make-from-real-imagxy)(consxy)(define(magnitudez)(sqrt(+(square(real-partz)(square(imag-partz)(define(anglez)(atan(imag-partz)(real-partz)(define(make-from-mag-angra)(cons(*r(cosa)(*r(sina),抽象数据的多重表示,;interfacetotherestofthesystem(define(tagx)(attach-tagrectangularx)(putreal-part(rectangular)real-part)(putimag-part(rectangular)imag-part)(putmagnitude(rectangular)magnitude)(putangle(rectangular)angle)(putmake-from-real-imagrectangular(lambda(xy)(tag(make-from-real-imagxy)(putmake-from-mag-angrectangular(lambda(ra)(tag(make-from-mag-angra)done),抽象数据的多重表示,我们可以看到这里所有的内部过程，与最开始定义的过程完全一样，将它们与系统的其他部分建立联系时，也不需要做任何修改。进一步说，由于这些过程定义都是上述安装过程内部的东西，故而完全不必担心它们的名字会与直角坐标程序包外面的其他过程的名字互相冲突。所以完全没有必要在加入系统时修改包内过程的名字。写出极坐标包的安装过程？,抽象数据的多重表示,复数算术的选择函数通过一个通用的名为apply-generic的“操作”过程访问有关表格，这个过程将通用型操作应用于一些参数。apply-generic在表格中用操作名和参数类型查找，如果找到，就去应用查找中得到的过程：(define(apply-genericop.args)(let(type-tags(maptype-tagargs)(let(proc(getoptype-tags)(ifproc(applyproc(mapcontentsargs)(errorNomethodforthesetypes-APPLY-GENERIC“(listoptype-tags),抽象数据的多重表示,利用apply-generic，各种