SICP 习题 (1.6) 解题总结:对if语句的特殊处理

SICP 习题 1.6 还是讲的正则序和应用序,问题是从if过程的讨论开始的,习题说到名叫Alyssa P. Hacker的人觉的不需要为if提供一种特殊形式,可以直接用常规过程调用cond来实现。

我第一次看到这道题的时候的完全不明白题目是什么意思,我当时的反应是,“if有特殊形式吗?”,我没觉的if有什么特殊呀。有这样的反应是因为没有认真思考习题1.5,这次做题目比较细致,做习题1.5的时候就想过,使用正则序展开过程的时候,不理会if,直接展开所有过程不是更简单一些吗?后来发现,不理会if,直接展开过程是会导致问题的,必须对if进行特殊的处理才能让解释器正常工作。

我们先回想一下习题1.5,我们上次看习题1.5的时候就看到习题有一个假设,就是不管是正则序还是应用序,都假设if过程对条件进行判断后只对条件成立对应的部分进行处理,忽略条件不成立对应部分的部分。

有了这个假设,可以发现习题1.5中的过程在应用序环境下会“死机”,而在正则序环境下会返回0。

而这种针对if过程的特殊处理就是if的特殊形式。

现在习题1.6问的问题就是针对if过程的这种特殊处理有必要吗,通过常规的过程处理会有什么问题。

解答这个问题的好方法就是建构一个常规的过程去代替if过程,看会出现什么问题。

习题种已经帮我们定义好了这个代替if的过程,叫做new-if,习题种讲到这个过程是Alyssa的朋友Eva Lu Ator做的,过程定义如下:

(define (new-if predicate then-clause else-clause) (cond (predicate then-clause)(else else-clause)))

这个new-if过程在处理一般参数时是没有问题的。做new-if过程的Eva做了一下测试,都没有问题:

(new-if (= 2 4) 0 5)(new-if (= 2 2) 0 5)

接着,如果Eva通过new-if来重写求平方根的过程,似乎就有点问题了。

有关原来版本的求平方根的过程,想详细了解的话需要回去看看1.1.7那节。1.1.7节讲了使用牛顿法求平方根,里面涉及的数学方法其实和本习题的目的没有关系,不过看到牛顿法优美的地方真的是让我这种没有数学天分的人叹为观止。所以,建议大家还是好好理解一下1.1.7节的内容,一是感受一下大师的风范,二是后面的其它习题和这个还有关系。

总之,原来的过程是这样的:

(define (sqrt-iter guess x)(if (good-enough? guess x)guess(sqrt-iter (improve guess x) x)))其中good-enough?和improve过程的实现就不贴出来了,不清楚的话需要回去看看1.1.7节,不过这些细节和本习题关系不大。

一切运行正常,如果改为new-if的过程就是这样的,很简单,就是将if换成了new-if

(define (sqrt-iter guess x)(new-if (good-enough? guess x)guess(sqrt-iter (improve guess x) x)))

会出什么问题呢?在mit-Scheme里跑一下以上代码就知道了,mit-Scheme又“死机”了。

为什么呢?来仔细看看,假设我们通过以下过程调用来测试,就是求16的平方更,从1开始猜,所以执行的代码如下:

(sqrt-iter 1 16)

展开就是:

(new-if (good-enough? 1 16)1(sqrt-iter (improve 1 16)16)))因为Scheme使用的是应用序,所以,对于过程new-if来讲,系统会希望计算所有参数的值,然后代换到new-if过程中,需要计算的包括:

(good-enough? 1 16)(sqrt-iter (improve 1 16) 16))

根据我们上面对于牛顿法的理解,我们知道(improve 1 16)会返回8.5,所以我们需要计算的其实是:

(sqrt-iter 8.5 16)

我们发现我们相当于回到了第一步计算(sqrt-iter 1 16)的时候,就是参数变了而已。我们需要继续展开sqrt-iter过程。

这个过程会一直持续下去,不断的递归调用。即使到我们的(good-enough? guess x)过程返回结果为真,以上过程还是会继续。关键就是我们使用了new-if过程,而不是if过程。

其中的差别就是new-if是常规过程,会使用应用序计算所有参数,而if过程有特殊处理,会根据条件判断的结果决定计算哪部分参数。

在Lisp环境中,我们经常会说我们定义的过程和系统过程没什么差别,其实,在关键的地方,我们定义的过程和系统过程的差别是很大的,只是我们一般不需要关注这些差别而已。

有了以上的结果,我们可以进一步考虑一下在正则序环境中使用new-if会是什么结果。

对于正则序的环境,它会将过程不断展开,直到所有元素都是基本元素,然后对展开的结果进行归约。

如果我们使用的是new-if,则以下部分会被展开:

(good-enough? guess x)(sqrt-iter (improve guess x) x)其中(improve guess x)可以直接展开,关键在于sqrt-iter过程,将sqrt-iter展开以后又是一个new-if过程, 其中继续包括下面两部分需要展开:(good-enough? guess x)(sqrt-iter (improve guess x) x)

所以会形成一个无限递归,不断地展开,不会因为 good-enough?过程的返回值而停止。

也就是说,不管是正则序还是应用序,使用new-if去代替if都会发生问题无限递归的问题。

这时候,回想我们在习题1.5中讨论的有关正则序的展开方式,我当时觉得理想的,优美的方式应该是对过程不断展开,直到没办法展开为止,然后再进行归约。但是这个理想的方式会导致大部分递归调用无法返回,,因为大部分递归调用都需要一个条件判断来决定是否继续进入递归过程,而不断展开的方式会忽略条件判断的结果,直接对过程的所有参数进行展开,从而导致问题。

有时,明知错了,却欲罢不能,

SICP 习题 (1.6) 解题总结:对if语句的特殊处理

相关文章:

你感兴趣的文章:

标签云: