过程作为黑箱抽象.ppt

过程作为黑箱抽象,sqrt程序的分解过程: 这里的关键问题是，分解中的每一个 过程完成了一件可以标明的工作，这 使它们可以被用作定义其他过程的模 块。我们可以将square看做一个黑箱， 根本无须关注该过程是如何计算出结 果的。更进一步，在相应过程还没有 写好之前，我们可以只关心square 这个名字，把它当做这个过程的抽象， 在这个抽象层次上任何能计算出平方 的过程都可以用。,过程作为黑箱抽象,可就是说，在只考虑过程的返回值时，下面两个过程应是不可区分的： (define (square x) (* x x) (define (square x) (exp (double (log x) (define (double x) (+ x x) 可见一个过程定义应该能隐藏起某些细节，使得过程使用者可能不必自己去写这些过程，而是从其他程序员那里作为黑箱接受过来。并且在使用时应该不需要去弄清楚它是如何实现的。,过程作为黑箱抽象,局部名： 过程用户不必关心实现细节之一就是过程里面的形式参数的名字，如 (define (square y) (* y y) (define (square x) (* x x) 这两个过程应该是无法区分的。 形式参数的具体名字是什么，完全没有关系，这样的名字称为约束变量，一个过程的定义约束了它的所有形式参数。如果在一个完整的过程定义里将某个约束变量同一换名(注意不要跟其他形参名一样，实际上过程的定义也不允许有相同的形参名)，这一过程定义的意义将不会改变。 不被约束的变量称为自由的。 一个名字的定义被约束于的那一集表达式称为这个名字的作用域 被声明为这个过程的形式参数的那些约束变量，就以这个过程体作为他们的作用域,过程作为黑箱抽象,内部定义和块结构： 我们再来回顾前面的sqrt程序，其由几个相互分离的程序组成，问题是这组程序只有sqrt对用户是重要的，其它过程则会带来干扰。因此我们希望能够将这种子过程局部化，将它们隐藏到sqrt的里面。 为使这种方式可能，我们要允许一个过程里面带有一些内部定义，使它们是局部于这一过程的。如：,过程作为黑箱抽象,平方根程序的内部定义表示： (define (sqrt x) (define (good-enough? guess x) ( (abs (- (square guess) x) 0.001) (define (improve guess x) (average guess (/ x guess) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x) (sqrt-iter 1.0 x) 这种嵌套的定义称为块结构。,过程作为黑箱抽象,平方根程序的内部定义表示： 分析上面的过程一种更好的想法是，没有必要显示的把x在内部过程中传来传去了，既然它们都在x的作用域里，我们可以直接给出如下定义： (define (sqrt x) (define (good-enough? guess) ( (abs (- (square guess) x) 0.001) (define (improve guess) (average guess (/ x guess) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess) (sqrt-iter 1.0) 这种方式叫做词法作用域。,线性的递归和迭代,考虑阶乘函数： (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1) 我们利用代换模型， 观看其求值的行为如图：,递归和迭代,计算阶乘函数的不同的观点： (define (factorial n) (fact-iter 1 1 n) (define (fact-iter product counter max-count) (if ( counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count),递归和迭代,计算阶乘函数的两种不同方法的比较： 第一个过程中，代换模型揭示出一种先逐步展开而后收缩的形状，展开阶段里，构造起一个推迟操作所形成的链条(如前面的乘法链条)，收缩阶段表现为这些运算的实际执行。 这种由一个推迟执行的运算链条刻画的计算过程，称为一个递归计算过程 与之相对应，第二个计算过程里并没有任何增长或收缩。对任何一个n，计算过程的每一步，我们需要保存轨迹里，所有的东西就是变量的当前值，我们称这种过程为一个迭代计算过程。一般来说，迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程；同时还存在一套固定的规则，描述了计算过程在状态转换时，变量的更新方式。 注意：不要混淆递归计算过程和递归过程的概念。递归过程是一个语法形式上的事实，说明一个过程定义中直接或间接引用了该过程本身。所以我们可以有如下陈述：一个递归过程将产生出一个迭代的计算过程。这是由于scheme中使用了一种称为尾递归的编译技术。,递归和迭代,树形递归： 计算斐波那契数列： (define (fib n) (cond (= n 0) 0) (= n 1) 1) (else (+ (fib (- n 1) (fib (- n 2) 考虑(fib 5)的计算过程： 可以证明计算步骤 相对于n是指数的 这是一种很糟糕的计算过程。 一般说，树形递归计算过程所需的步骤数正比与书中的结点数，空间需求正比于树的最大深度。,递归和迭代,计算斐波那契数列的迭代过程： (define (fib n) (fib-iter 1 0 n) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1) 所需的步骤数相对于n是线性的 但我们也不应作出结论说递归计算过程根本没用。相反递归计算过程很自然，往往就是算法的直接翻译，能帮助我们理解和设计程序，而要规划出迭代过程，就不那么明显了。,实例研究：数的求幂,问题描述： 计算出bn的值，我们有递归定义： bn=b*bn-1 b0=1 直接翻译如下： (define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1) 这是一个线性递归计算过程，需要O(n)步和O(n)空间,实例研究：数的求幂,等价的线性迭代过程如下： (define (expt b n) (expt-iter b n 1) (define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product) 需要O(n)步和O(1)空间,实例研究：数的求幂,算法的改进： 我们可以通过连续求平方，以更少的步骤完成乘幂的计算。如： b2=b*b b4=b2*b2 b8=b4*b4 三次乘法就可以把b8算出来，而开始的算法主要计算7次乘法。 (define (fast-expt b n) (cond (= n 0) 1) (even? n) (square (fast-expt b (/ n 2) (else (* b (fast-expt b (- n 1) even?是检测一个整数是否是偶数的谓词 (define (even? n) (= (remainder n 2) 0) 这是一个递归计算过程，该过程的增长阶为O(logn) 给出该过程相应的迭代算法？,用高阶函数做抽象,如果将过程限制为只能以数作为参数，那也会严重地限制我们建立抽象的能力。经常有一些同样的程序设计模式能用于若干不同的过程。为了把这种模式描述为相应的概念，我们就需要构造出这样的过程，让他们以过程作为参数，或者以过程作为返回值。这类能操作过程的过程称为高阶过程,用高阶函数做抽象,过程作为参数： 考虑下面3个过程： 1.计算从a到b的各整数之和： (define (sum-integers a b) (if ( a b) 0 (+ a (sum-integers (+ a 1) b) 2.计算给定范围内的整数的立方之和： (define (sum-cubes a b) (if ( a b) 0 (+ (cube a) (sum-cubes (+ a 1) b),用高阶函数做抽象,3.计算下面的序列之和： 1/(1*3)+ 1/(5*7)+ 1/(9*11)+ 它将收敛到/8： (define (pi-sum a b) (if ( a b) 0 (+ (/ 1.0 (* a (+ a 2) (pi-sum (+ a 4) b) 可以明显看出上面三个过程共享着一种公共模式：其形式如下： (define ( a b) (if ( a b) 0 (+ ( a) ( ( a) b),用高阶函数做抽象,这种公共模式的存在是一种很强的证据，说明这里实际上存在着一种很有用的抽象，确实这里用到了求和这一抽象概念，数学家在很早以前就使用了专门的记号，如： , 这种记法的威力就在于它使数学家能去处理求和的概念本身，而不只是某个特定的求和。 在这里我们自然希望在使用的程序设计语言中也能写出这一抽象的过程，而不是只能写计算特定求和的过程。所幸的是我们所使用的语言提供了这种机制。,用高阶函数做抽象,按照上面的模式，将其中“空位”翻译为形式参数： (define (sum term a next b) (if ( a b) 0 (+ (term a) (sum term (next a) next b) 过程sum体现出的就是求和概念的本身，即： 这里的函数f就对应上面的term，不过sum过程还有一个过程参数next，它的作用是用来产生后继的求和参数。 这样我们就可以用sum过程来定义其他各种具体的求和过程了。,用高阶函数做抽象,例如： 我们可以用sum重新定义sum-cubes过程如下： (define (cube x) (* x x x) (define (inc n) (+ n 1) (define (sum-cubes a b) (sum cube a inc b) 重新定义sum-integers过程如下： (define (identity x) x) (define (sum-integers a b) (sum identity a inc b),用高阶函数做抽象,重新定义pi-sum过程如下： (define (pi-sum a b) (define (pi-term x) (/ 1.0 (* x (+ x 2) (define (pi-next x) (+ x 4) (sum pi-term a pi-next b) 利用这一过程就能计算的一个近似值了： (* 8 (pi-sum 1 1000) 3.139592655589783 思考： 利用sum定义函数的近似积分过程(integral f a b dx)，利用如下公式：,用高阶函数做抽象,用lambda构造匿名过程 在前面如果我们要用到一个过程，就必须先给该过程定义一个名称，然后再在其他过程中通过名字使用该过程。这里我们给出一种定义匿名过程的方法，我们通过引入一种lambda特殊形式完成。 一般而言，lambda用与define同样的方式创建过程，除了不为有关过程提供名字之外：语法形式如下： (lambda () ) 例如我们可以定义： (lambda (x) (+ x 4) 相应的define定义： (define (plus x) (+ x 4) 等价于: (define (plus x) (lambda (x) (+ x 4) 我们可以按如下方式来阅读lambda表达式： (lambda (x) (+ x 4)：(该过程 (以x为参数) (它加起 x 和4),用高阶函数做抽象,我们用lambda重新定义pi-sum过程如下： (define (pi-sum a b) (sum (lambda (x) (/ 1.0 (* x (+ x 2) a (lambda (x) (+ x 4) b) 请利用lambda重新定义过程integral？,用高阶函数做抽象,用let创建局部变量： 考虑计算函数：f(x,y)=x(1+xy)2+y(1-y)+(1+xy)(1-y) 我们可能希望将它表述为： a=(1+xy) b= (1-y) f(x,y)=xa2+yb+ab 所以在写f的过程时,我们希望有局部变量，而不止是参变量x和y。为做到这点我们可以用一个匿名的辅助过程来实现，如下： (define (f x y) (lambda (a b) (+ (* x (square a) (* y b) (* a b) (+ 1 (* x y) (- 1 y),用高阶函数做抽象,在我们的程序设计中这一结构非常具有普遍性，因此，语言里专门有一个特殊形式称为let，使这种编程方式更为方便。一般形式为： (let ( ) ( ) ( ) ) 解释器把let表达式解释为lambda表达式的一种语法外衣，形式如下： (lambda ( ) ) ) 根据这一等价，let表达式描述的变量的作用域就是该let的体，这使我们可以在接近使用的地方创建局部变量,用高阶函数做抽象,利用let，过程f可以重写如下： (define (f x y) (let (a (+ 1 (* x y) (b (- 1 y) (+ (* x (square a) (* y b) (* a b),用高阶函数做抽象,实例研究：找出函数的不动点 问题描述： 称数x为函数f的不动点，如果x满足f(x)=x，对于某些函数，通过从某个初始猜测出发，反复地应用f直到值的变化不大时，就可以找到它的一个不动点。f(x),f(f(x),f(f(f(x), 根据这个思路我们设计一个过程fixed-point，反复应用这个函数，直到发现连续的两个值之差小于某个并事先给定的容许值。,用高阶函数做抽象,(define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) ( (abs (- v1 v2) tolerance) (define (try guess) (let (next (f guess) (if (close-enough? guess next) next (try next) (try first-guess),用高阶函数做抽象,这一过程类似于我们前面讲的sqrt的过程，事实上，我们完全可以将平方根的就算形式化为一个不动点的计算过程。将有y2=x化为y=x/y，可以发现，这里要做的就是寻找函数y=x/y的不动点。如： (define (sqrt x) (fixed-point (lambda (y) (/ x y) 1.0) 但是该过程不动点的搜寻并不收敛，我们改进算法如下： (define (sqrt x) (fixed-point (lambda (y) (average y (/ x y) 1.0) 应为实际答案总是在两个猜测y和x/y之间，为此可以用y和x/y的平均值做猜测值。这种取逼近一个解的一系列值的平均值的方法，是一种称为平均阻尼的技术。,用高阶函数做抽象,过程作为返回值： 考虑前面的不动点搜寻的算法，我们利用了平均阻尼使这一逼近收敛。但平均阻尼也是一种很有用的一般性技术。很自然，我们希望单独考虑这一思想：给定一个函数f后，我们可以考虑另一个函数，它在x处的值等于x和f(x)的平均值。 我们可以表述如下： (define (average-damp f) (lambda (x) (average x (f x) 利用average-damp我们可以重写平方根过程如下： (define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y) 1.0),用高阶函数做抽象,实例研究：牛顿法求函数的零点 问题描述：如果g(x)是一个可微函数，那么g(x)=0的一个解就是 f(x)=x