练习1.6

这道题目考察的认识应用序和正则序的区别 题目背景是默认的应用序求值顺序

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

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

当Alyssa使用上述过程来计算平方根的时候 将会被解释器告知

函数的递归层数太深了 超过了最大的递归深度

正是应用序的求值顺序导致了这样的错误发生

首先 让我们来看一下if和new-if的区别在哪里

根据书上定义 if的执行规则是这样的：

首先对谓词求值 如果谓词求值结果为真 那么就求值consequence部分并返回 否则求值alternative部分并返回（如果存在）

但new-if作为用户自定义的普通函数 根据应用序它的求值规则为：

首先解释器对predicate then-clause else-clause分别求值 然后根据求值结果返回

从以上论述我们可以发现 执行new-if是 无论predicate为真还是为假 then-clause和else-clause都会被求值

因此 根据代换模型

(sqrt-iter guess x)

会被代换为

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

会被代换为

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

;improved-guess为(improve guess x)的求值结果

于是sqrt-iter会被解释器无限展开 从而导致递归过深 栈溢出

不过同时我们看到 因为传入sqrt-iter的是improved-guess而不是原先的guess 那么 平方根照样可以求得 它只是无法被传递出来了

那么 如果解释器采用正则序 这个程序会正常运行吗？

答案是肯定的

老样子 让我们使用代换模型

(sqrt-iter guess x)

会被代换为

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

会被代换为

(cond ((good-enough? guess x) guess)
      (else (sqrt-iter (improve guess x)
                       x)))

在此时 如果good-enough?求值为真 那么就会被代换为

guess

于是顺利求得平方根并返回

一个额外的问题是关于尾递归 我们知道 scheme的解释器带有尾递归优化 尾递归函数不会造成栈溢出 最多只会进入死循环

但可惜 虽然sqrt-iter看上去十分符合尾递归的特征 但由于sqrt-iter的值需要被new-if作为参数使用 所以对sqrt-iter的调用并不是尾递归的

所以这个习题告诉我们 乱装x可能会出大事情 XD