鸿 网 互 联 www.68idc.cn

计算机中的黑魔法:尾递归

来源:互联网 作者:佚名 时间:2015-07-26 20:29
至于把正常递归转化为尾递归的方法,我觉得比较直接的做法就是,正常递归是从后向前考虑,如果写尾递归,那么就把问题从前向后考

声明:本文是作者在学习SICP有关过程抽象知识的理解,由于书中的语句有些晦涩,所以将作者的理解共享给大家希望帮助一些朋友。原书对尾递归并没有太多介绍,但是这里给出了详细的解释。

目前是凌晨1点48分。嗯,刚刚写完这篇日志。忍不住想说点什么,或许是当一个不好的书托。可能这些内容对于很多人来说是没有用的,他们甚至会鄙视我写的东西,觉得为这些东西花费时间不值得。对于这些人,我想说,每一个对计算机有着浓厚兴趣的人,都有着一个想够彻头彻尾了解每天超过12小时面对的这台机器是如何工作的愿望。像SICP和CSAPP这种书无疑是枯燥的,你可能一天看下来,仔细品读的话只能看三四页,但是如何你能够真正理解这几页书的内涵的话,那么收获将是巨大的。从去年5月份,陈大师推荐我读CSAPP之后,我才真正找到了那种看上去很枯燥,但是一读起来就欲罢不能的书。这类的书读起来都很困难,如果你带着很强的功利性来读的话,是不可能读下去的。我想了想,能够支撑我一天坐在那琢磨这几页书中说的核心意思的力量,就是来源于我真正想了解计算机是怎么工作的,获取这种信息对于我来说是非常快乐的,这种感觉是奇妙的。

函数和计算过程的区别

函数一般是指数学上面的一种计算形式,偏向说明语句,描述如何根据给定的一个或者几个参数去计算出一个值。如SICP中关于求一个数的平方根的函数,我们在该函数的说明中可以推断出关于平方根的一些具体性质和一般性的事实,但是我们无从得知计算一个数的平方根的具体方法。你可能会说,求平方根不就是开根号么。可是你有没有想过,[开根号]也仅仅是一个说明性的语句,具体怎么计算你还是不知道的。延伸到计算机当中的函数,其实和数学上面的函数意义是相同的,我们只不过是换成高级程序设计语言来写我们对于一个函数一般性事实的说明,,实际上我们并没有给出一个具体的计算过程。比如求平方根,如果我们是调用math.h中的库函数来求的话:sqrt(x*1.0),这种形式只是一个说明型的语句,我们利用这个语句来指导计算机去计算,但实际上这个函数并没有提供具体的计算过程。计算机当中的解释器就负责把这种说明性语句转化成真正的计算过程(期待到时候写一个解释器哇)。

其实感觉这两者的区别就和写作文一样,一个是提纲,另外一个是具体的内容。

触摸过程的抽象

SICP中关于求一个数平方根的问题,使用的是牛顿的逐步逼近法则,不断的去求新的猜测值,直到结果满足一定的精度结束。求平方根是一个大的功能,想要完成这个大的功能还需要一些小的功能来辅助。

过程抽象的实质就是一种功能的分解

我们把整个一个大的计算过程分为几个部分,每一个部分都能单独完成其中的一个小功能,他们组合起来又能够完成最终的功能。所谓过程的抽象和C++中的面向对象思想是和相像的,没准都是一个东西,我不太确定,但是过程的抽象说的都是一个意思,就是对创造者来说重要的是过程的实现,而对于使用者来说,过程的抽象可以屏蔽掉内部实现的细节,从而减轻使用者的负担,只关心这个过程的『黑盒』能够做什么。所以这样一来就增加了程序局部的可替换性,因为对于实现一个功能来说,过程的内部实现可以多种多样。

抽象1—局部名字

大家都知道调用函数或者过程的时候,有的时候需要传递一些合适的参数,在调用的过程中,函数的形式参数的名字对我们来说其实并不重要,相对于使用者来说确实是这样。但是对于过程的设计者来说,形式参数的名字,或者说是局部变量的名字,对于整个过程能够正常的执行就非常重要了。这也是过程抽象当中的一个细节,计算机把一些复杂的东西封装到了内部。

关于过程的抽象中可能会有两个新的概念,约束变量和自由变量。单就一个过程来讲,我的理解是约束变量就是一种名字是什么无所谓,但是统一换名之后不改变过程意义的一种变量,他有自己的作用域,类比于局部变量吧。而自由变量就类比于全局变量,或者静态变量,我是这么理解的。约束变量的名字并不重要,重要的是哪些地方用了同一个约束变量。

为什么说约束变量的名字对于过程的执行是非常重要的呢。很直接的一个理解就是:局部变量可以在作用域内可以屏蔽同名的全局变量,类比一下,约束变量在相应的作用域内会屏蔽同名的自由变量。

(define (good-enough? guess x) ((abs (- (square guess) x)) 0.001))

举例来讲,在上面这个过程中,guess 和 x 是good-enough?这个过程的两个约束变量,<, abs, -, square都是自由变量。自由变量是和环境相关的,他们已经有了确定的意义来保持他们正常的执行,但是如果现在guess这个约束变量改名为abs,将会导致abs这个自由变量的意义被约束变量屏蔽,过程中出现的abs为约束变量,不在具有自由变量当中求绝对值的功能。

所以说,对于过程的设计者而言,过程实现中,自由变量和约束变量的名字都在哪些地方用到是一个非常需要注意的地方,一个过程的顺利执行依赖于约束变量和自由变量的名字不同,并且自由变量的意义正确。

抽象2—内部定义和块结构

这一点的抽象就更加为我们过程的使用者考虑,它也是一种局部的概念,像局部变量一样,只有内部的作用域可以访问并且识别他,作用域之外是不知道作用域内有这个东西的。只不过我们之前抽象的是变量,这次抽象的是过程。

sicp中的求平方根的过程,和用户交互的仅仅是一个接口sqrt,其中的子过程的具体实现细节都被抽象一个个的【黑箱】。但是对于用户来说,这些实现计算过程的黑箱是没有用的,只会扰乱他们的思维,并且在用户想自定义一个与这些黑箱中的某一个同名的过程的时候是不被允许的(不能在一个作用域内定义两个同名的过程),这些有着具体功能的【黑箱】污染了全局名字环境。

对于一个结构局部的东西,我们更好的方式是把他们定义在这个结构的内部,而不应该放在全局环境范围内,因为你需要的并不是其他人也需要的,如果其他人不需要这些东西,那么他们的命名就有可能造成过程调用的命名冲突,造成程序混乱。

scheme支持在过程的内部再定义新的过程,内部新定义的过程只能在内部作用域可见,外部是不知道有内部这些过程的定义的。

(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))
网友评论
<