sicp02-3

程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 技术和 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 裘宗燕，2009-2010 -1- 2. 构造数据抽象(3) 本节讨论 „ 分层抽象 „ 通用型算术运算 „ 不同类型数据的组合 „ 符号代数 „ 多项式算术 程序设计技术和方法 裘宗燕，2009-2010 -2- 有通用型操作的系统 „ 前面做了有理数算术包和复数算术包，还有系统提供的常规算术系统。 现在考虑如何通过数据导向程序设计技术把这些算术系统集成到一个系 统里，展示定义针对不同参数类型的通用型操作的技术 完成的系统具有下面结构： add sub mul div add-complex sub-complex mul-complex div-complex + - * / add-rat sub-rat mul-rat div-rat 常规算术有理数算术 复数算术 使用算术系统的程序 通用型算术包 极坐标 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示直角坐标表示 表结构和基本算术系统 ■ 还进一步希望做出的系统有可加性，其他独立设计的算术包很容易组合 到这个系统里 程序设计技术和方法 裘宗燕，2009-2010 -3- 通用型算术运算 „ 希望整个系统有一个通用加法运算，对常规的数其行为如同 +；对有理 数它如同 add-rat；对复数如同 add-complex。其他算术运算类似 „ 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 用前一节开发的技术，为每个类型附加标签，让通用型 add 等运 算根据运算对象的标签选择正确的指派 „ 几个通用型运算过程的定义如下： (define (add x y) (apply-generic 'add x y)) (define (sub x y) (apply-generic 'sub x y)) (define (mul x y) (apply-generic 'mul x y)) (define (div x y) (apply-generic 'div x y)) 这几个过程将根据运算对象的类型，从表格里提取正确操作 程序设计技术和方法 裘宗燕，2009-2010 -4- 通用型算术运算：常规数 „ 常规 Scheme 数加标签 scheme-number。每个算术运算都是两个参 数，关键码用 (scheme-number scheme-number) (define (install-scheme-number-package) (define (tag x) (attach-tag 'scheme-number x)) (put 'add '(scheme-number scheme-number) (lambda (x y) (tag (+ x y)))) (put 'sub '(scheme-number scheme-number) (lambda (x y) (tag (- x y)))) (put 'mul '(scheme-number scheme-number) (lambda (x y) (tag (* x y)))) (put 'div '(scheme-number scheme-number) (lambda (x y) (tag (/ x y)))) (put 'make 'scheme-number (lambda (x) (tag x))) 'done) „ 创建带标志的常规数： (define (make-scheme-number n) ((get 'make 'scheme-number) n)) 其他类型的数按同样 方式加入这个系统 程序设计技术和方法 裘宗燕，2009-2010 -5- 通用型算术运算：有理数 „ 已有的有理数功能可以直接作为内部过程加进来，无须修改 (define (install-rational-package) ;; internal procedures (define (numer x) (car x)) (define (denom x) (cdr x)) (define (make-rat n d) (let ((g (gcd n d))) (cons (/ n g) (/ d g)))) (define (add-rat x y) (make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) ... ... ... ;; interface to rest of the system (define (tag x) (attach-tag 'rational x)) (put 'add '(rational rational) (lambda (x y) (tag (add-rat x y)))) ... ... ... (put 'make 'rational (lambda (n d) (tag (make-rat n d)))) 'done) (define (make-rational n d) ((get 'make 'rational) n d)) (define (sub-rat x y) (make-rat (- (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) (define (mul-rat x y) (make-rat (* (numer x) (numer y)) (* (denom x) (denom y)))) (define (div-rat x y) (make-rat (* (numer x) (denom y)) (* (denom x) (numer y)))) (put 'sub '(rational rational) (lambda (x y) (tag (sub-rat x y)))) (put 'mul '(rational rational) (lambda (x y) (tag (mul-rat x y)))) (put 'div '(rational rational) (lambda (x y) (tag (div-rat x y)))) 程序设计技术和方法 裘宗燕，2009-2010 -6- 通用型算术运算：复数 „ 将类似前面定义的复数包安装到系统里，加标签 complex： (define (install-complex-package) ;; imported procedures from rectangular and polar packages (define (make-from-real-imag x y) ((get 'make-from-real-imag 'rectangular) x y)) (define (make-from-mag-ang r a) ((get 'make-from-mag-ang 'polar) r a)) ;; internal procedures (define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2)))) ... ... ... ;; interface to rest of the system (define (tag z) (attach-tag 'complex z)) (put 'add '(complex complex) (lambda (z1 z2) (tag (add-complex z1 z2)))) ... ... ... (put 'make-from-real-imag 'complex (lambda (x y) (tag (make-from-real-imag x y)))) (put 'make-from-mag-ang 'complex (lambda (r a) (tag (make-from-mag-ang r a)))) 'done) 操作在内部定义， 各包里都直接用过 程名 add, sub, mul, div 程序设计技术和方法 裘宗燕，2009-2010 -7- 通用型算术运算：复数 „ 外部可以用实部/虚部或模/幅角的方式创建复数，为此需要从直角坐标 和极坐标包里导出相应过程，定义相应的全局构造函数： (define (make-complex-from-real-imag x y) ((get 'make-from-real-imag 'complex) x y)) (define (make-complex-from-mag-ang r a) ((get 'make-from-mag-ang 'complex) r a)) „ 这是一个有两重标签的系统：外层标签辨别数的种类（有理数/复数/常 规数）。对复数，内层标签标明表示方式。如 3 + 4i： ■ 复杂系统可能有许多层次，不同层次之间通过一组通用操作互联，这些 操作基于数据上的标签区分不同数据类别 ■ 数据“向下”传输时逐步剥离一层层标签；“向上”传输过程中一层层增加 数据标签（例如网络传输） 程序设计技术和方法 裘宗燕，2009-2010 -8- 不同类型的数据的组合 „ 现在有了一个支持多种数的运算的系统，但它有一个重大缺点：不同类 型的数属于不同的独立“世界”，相互无联系 „ 实际中常要做不同类型数据之间的操作。这里就是跨越类型运算。前面 设计中仔细在程序各部分之间设计了清晰的隔离。引进跨类型操作必须 仔细考虑，使系统既能支持这类操作又不严重损害原有模块分隔 „ 实现跨类型操作的一种方式是为每对类型组合定义一个新操作。如对复 数与常规数求和，用标签 (complex scheme-number) 加入过程： ;; to be included in the complex package (define (add-complex-to-schemenum z x) (make-from-real-imag (+ (real-part z) x) (imag-part z))) (put 'add '(complex scheme-number) (lambda (z x) (tag (add-complex-to-schemenum z x)))) „ 这样做太麻烦。n 种类型 m 种操作需要 m*n*(n-1) 个混合操作。加入 一个新类型，不仅要定义它本身的操作，还需定义它与各已有相关类型 的混合操作，已有类型和它的混合操作。在哪里定义也是个问题 程序设计技术和方法 裘宗燕，2009-2010 -9- 不同类型的数据的组合：强制 „ 在处理几种相互无关的数据和相互无关的操作时，直接定义跨类型操作 可能是最好的方法，虽然做起来比较麻烦。许多情况下，可能利用类型 系统之间的一些隐含关系把事情做得更好 „ 不同数据类型间常有某种关系，例如一种类型的对象可看作另一种类型 的对象，这种看法称为强制（coercion）。例如：常规的数可以看成虚 部为 0 的复数，它与复数的运算可以转化为复数运算 „ 实现这种想法需要开发一些强制过程。例如 (define (scheme-number->complex n) (make-complex-from-real-imag (contents n) 0)) 把它们安装到一个特殊的强制表格里（假设存在put-coercion 和 get- coercion 过程，对这个表格操作）： (put-coercion 'scheme-number 'complex scheme-number->complex) „ 如果不允许做某种自动强制，强制表中就不放相关的项。例如，可以不 允许从复数到常规数的转换 程序设计技术和方法 裘宗燕，2009-2010 -10- 不同类型的数据的组合：强制 „ 安好所有强制过程后还要修改 apply-generic，统一处理强制问题 „ 新 apply-generic 先检查能否直接计算，如能就直接指派；否则就考虑能否强 制（这里只考虑了两个参数的情况）： (define (apply-generic op . args) (let ((type-tags (map type-tag args))) (let ((proc (get op type-tags))) (if proc (apply proc (map contents args)) (if (= (length args) 2) (let ((type1 (car type-tags)) (type2 (cadr type-tags)) (a1 (car args)) (a2 (cadr args))) (let ((t1->t2 (get-coercion type1 type2)) (t2->t1 (get-coercion type2 type1))) (cond (t1->t2 (apply-generic op (t1->t2 a1) a2)) (t2->t1 (apply-generic op a1 (t2->t1 a2))) (else (error "No method for these types" (list op type-tags)))))) (error "No method for these types" (list op type-tags))))))) 程序设计技术和方法 裘宗燕，2009-2010 -11- 类型的分层结构 „ 用强制技术实现类型互操作的优点：每对类型只需一个过程（如直接做 混合类型运算，对每个通用过程，每对类型需要一个具体版本）。这样 做的条件是所需转换只依赖于类型，与具体操作无关 „ 更复杂情况可能需要把两个类型转到另一个公共类型（下面讨论） „ 能用上述简单强制模型，要求各对类型间有某种简单关系 „ 例：算术系统存在一个类型分层：整数是有理数的子集， 有理数是实数的子集，实数是复数的子集。人们称这种结 构为“类型塔”（右图，是全序） 复数 实数 有理数 整数 ■ 对具有塔式结构的一组类型，可以采用一种统一模式设计 相关的强制过程：对较低类型的运算对象逐步强制，直至 两个运算对象的类型相同 ■ 类型具有塔式结构时还可能做向下转换。例如，若计算结 果是复数 4.3 + 0i，可以将其转换为实数 4.3 程序设计技术和方法 裘宗燕，2009-2010 -12- 分层结构的不足 „ 分层结构可能不足 以表达某些类型之 间的复杂关系 „ 例：由折线段表示 的各种 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的封闭 几何图形 „ 在复杂的类型关系 结构中，向上强制 或向下转换都可能 变得很复杂 „ 特别是存在多个向 上强制可能性时（ 面向对象里的多重 继承） 多边形 梯形 菱形 平行四边形 长方形 正方形 等腰直角 三角形 等边 三角形 四边形 筝形 等腰 三角形 直角 三角形 三角形 程序设计技术和方法 裘宗燕，2009-2010 -13- 实例：符号代数 „ 实例：一个符号计算系统 „ 这种系统很复杂，可表现许多在设计和实现大型系统时会遇到的问题 „ 代数表达式具有层次性结构，一个代数表达式可以看作从基本运算对象 出发，用运算符和函数等构造而形成的一棵树 ‰存在若干类基本运算对象，如数和变量 ‰存在一组运算符，如加减乘除。可能更多（如各种函数） ‰各种运算符和函数可以看作表达式复合的类型 „ 下面考虑开发一个完整的符号代数系统，其中集中关注多项式算术 „ 下面设计中，将特别考虑如何利用数据抽象和通用型操作的思想，构造 出一个结构良好，易于扩充的系统 程序设计技术和方法 裘宗燕，2009-2010 -14- 符号代数：多项式算术 „ 多项式是基于一个或多个未定元（变量），通过乘和加构造起来的代数 式。下面将多项式定义为某个未定元的项的和式，一个项可以是 ‰ 一个系数 ‰ 该未定元的乘方 ‰ 一个系数与未定元的乘方的乘积 ‰ 项的系数又可以是任意的多项式，但它不依赖于当前的未定元 „ 例如： ■ 这里把多项式看作一种特殊的语法形式，而不是它所表示的数学对象。 例如，这里不认为下面两个多项式等价： 程序设计技术和方法 裘宗燕，2009-2010 -15- 符号代数：多项式算术 „ 下面考虑如何实现多项式算术。先考虑把多项式表示为名为 poly 的数 据结构，它由一个变量（符号）和一组项构成 ‰选择函数 variable 和 term-list 提取表达式的两个部分 ‰构造函数 make-poly，从变量和项表构造多项式 „ 实现多项式加法和乘法的过程： (define (add-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (make-poly (variable p1) (add-terms (term-list p1) (term-list p2))) (error "Polys not in same var -- ADD-POLY" (list p1 p2)))) (define (mul-poly p1 p2) (if (same-variable? (variable p1) (variable p2)) (make-poly (variable p1) (mul-terms (term-list p1) (term-list p2))) (error "Polys not in same var -- MUL-POLY" (list p1 p2)))) 程序设计技术和方法 裘宗燕，2009-2010 -16- 多项式算术包 „ 要把多项式放进前面的通用算术系统里，需要为它提供一种标签。下面用标签 polynomial，相关操作也安装到操作表里： (define (install-polynomial-package) ;; internal procedures. First, representation of poly (define (make-poly variable term-list) (cons variable term-list)) (define (variable p) (car p)) (define (term-list p) (cdr p)) ;; representation of terms and term lists (define (add-poly p1 p2) ...) ... ;; (define (mul-poly p1 p2) ...) ... ;; ;; interface to rest of the system (define (tag p) (attach-tag 'polynomial p)) (put 'add '(polynomial polynomial) (lambda (p1 p2) (tag (add-poly p1 p2)))) (put 'mul '(polynomial polynomial) (lambda (p1 p2) (tag (mul-poly p1 p2)))) (put 'make 'polynomial (lambda (var terms) (tag (make-poly var terms)))) 'done) 程序设计技术和方法 裘宗燕，2009-2010 -17- 多项式算术：项表的加法 „ 多项式加法通过项表的加法实现，需要把未定元幂次相同的项相加，得到和式 中各项的系数。项表看作数据抽象：谓词 empty-termlist? 判断项表是否空， first-term 取出最高次项，rest-terms 取得其余项的表。 „ 项也是数据抽象，构造函数是 make-term，选择函数是 order 和 coeff „ 项表求和过程如下： (define (add-terms L1 L2) (cond ((empty-termlist? L1) L2) ((empty-termlist? L2) L1) (else (let ((t1 (first-term L1)) (t2 (first-term L2))) (cond ((> (order t1) (order t2)) (adjoin-term t1 (add-terms (rest-terms L1) L2))) ((< (order t1) (order t2)) (adjoin-term t2 (add-terms L1 (rest-terms L2)))) (else (adjoin-term (make-term (order t1) (add (coeff t1) (coeff t2))) (add-terms (rest-terms L1) (rest-terms L2))))))))) 注意：这里用通用过程 add 求两个系数之和。这一做法非常重要（后面解释） 程序设计技术和方法 裘宗燕，2009-2010 -18- 多项式算术：项表的乘法 „ 求两个项表之积的方法是逐个用第一个表的项乘第二个表中的各项（用 mul-term-by-all-terms），并将这样得到的项表累加起来。两个项的乘 积由其系数之积和次数之和构成 (define (mul-terms L1 L2) (if (empty-termlist? L1) (the-empty-termlist) (add-terms (mul-term-by-all-terms (first-term L1) L2) (mul-terms (rest-terms L1) L2)))) (define (mul-term-by-all-terms t1 L) (if (empty-termlist? L) (the-empty-termlist) (let ((t2 (first-term L))) (adjoin-term (make-term (+ (order t1) (order t2)) (mul (coeff t1) (coeff t2))) (mul-term-by-all-terms t1 (rest-terms L)))))) 程序设计技术和方法 裘宗燕，2009-2010 -19- 多项式算术：数据导向 „ 由于操作都基于通用算术过程实现，这一多项式算术系统自动地可以处 理任何（算术包能处理的）系数类型 ‰ 由于有前面定义的强制，不同类型的数可以相互运算 ‰ 为支持各种多项式的运算，还需增加把数强制到多项式的能力（一 个数就是一个 0 次多项式） „ 例如 系统计算系数时通过通用的 add 和 mul 指派。由于系数也是多项式， 这时会自动去调用多项式运算 add-poly 和 mul-poly 这样产生了数据导向的递归，每层都根据被运算数据的类型处理 „ 还可以重新考虑不同变量的多项式之间的关系。例如 2 x + 4 和 2 y – 1 求和，可以把后一多项式看作 x 的 0 次多项式 将这种考虑严格化，需要给变量排一个顺序（请自己想想） 程序设计技术和方法 裘宗燕，2009-2010 -20- 多项式算术：项表的表示 „ 还要考虑项表的实现 ‰ 项表是以次数为键值的系数集合，可采用能表示集合的任何技术 ‰ 需要按降幂顺序使用表中各项，因此要用某种排序表示 „ 考虑项表表示的一个因素是项的稠密性，看下面多项式： ■ 稠密多项式可以直接用项的表表示，如 (1 3 1 0 -1 6)。稀疏多项式 最好用两项表的表的形式，例如 ((1000 1) (10 -2) (0 5))。（显然也可 以考虑用序对的表） ■ 实际上，也可以考虑两种表示共存的系统（像前面的复数算术系统）， 加一层数据封装 ■ 下面采用后一种方式，项表里的项按降幂顺序排列 程序设计技术和方法 裘宗燕，2009-2010 -21- 多项式算术：项表的实现 „ 选好数据表示之后，项表的实现很简单： (define (adjoin-term term term-list) (if (=zero? (coeff term)) term-list (cons term term-list))) (define (the-empty-termlist) '()) (define (first-term term-list) (car term-list)) (define (rest-terms term-list) (cdr term-list)) (define (empty-termlist? term-list) (null? term-list)) (define (make-term order coeff) (list order coeff)) (define (order term) (car term)) (define (coeff term) (cadr term)) „ 创建多项式的过程： (define (make-polynomial var terms) ((get 'make 'polynomial) var terms)) 注意：=zero? 应为通用型过程 不难在算术包中加入这一谓词 程序设计技术和方法 裘宗燕，2009-2010 -22- 符号代数包中类型的分层结构 „ 这个系统说明：一种类型的对象可能有很复杂的结构，以许多不同类的 对象作为其组成部分。但通用操作的定义不会因此变得更困难 „ 这里先定义好针对复杂复合对象中各种成分的操作，安装适当的通用型 过程。数据导向的程序设计技术完全可以处理具有任意复杂的递归结构 的数据对象 „ 在多项式代数系统里，多种有关数据类型无法安排到一个类型塔里。例 如 x 的多项式和 y 的多项式哪个更高？可能解决办法： ‰ 实现多项式转换，把一个变量的多项式变换为另一个变量的多项式 （展开并重新整理） ‰ 变元排序，多项式总保持为某种“规范形式”（最外变元的优先级最 高，依次类推）。这种技术被广泛使用，但它有时可能不必要地扩 大了多项式的规模，并使其更难读 „ 设计大型代数演算系统时强制问题可能变得很复杂，不好控制。但另一 方面，已有技术为构造大型系统提供了很好支持 程序设计技术和方法 裘宗燕，2009-2010 -23- 总结 „ 数据抽象的意义 „ 构造数据抽象的基本过程和设计原则 „ 闭包性质的意义 „ 通用型过程 „ 消息传递风格的程序设计 „ 数据导向的程序设计 „ 基于数据导向和通用型操作实现复杂系统的技术