练习 1.6

以下是 Alyssa 的 new-if 定义:

;;; 6-new-if.scm

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

先使用 new-if 重写平方根过程:

;;; 6-sqrt-iter.scm

(load "6-new-if.scm")

(load "p15-good-enough.scm")                ; 定义平方根用到的其他函数
(load "p15-improve.scm")
(load "p16-sqrt.scm")

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)          ; <-- new-if 在这里
            guess
            (sqrt-iter (improve guess x)
                        x)))

然后将程序放进解释器尝试求值:

1 ]=> (load "6-sqrt-iter.scm")

;Loading "6-sqrt-iter.scm"...
;  Loading "6-new-if.scm"... done
;  Loading "p15-good-enough.scm"... done
;  Loading "p15-improve.scm"...
;    Loading "p15-average.scm"... done
;  ... done
;  Loading "p16-sqrt.scm"...
;    Loading "p15-sqrt-iter.scm"...
;      Loading "p15-good-enough.scm"... done
;      Loading "p15-improve.scm"...
;        Loading "p15-average.scm"... done
;      ... done
;    ... done
;  ... done
;... done
;Value: sqrt-iter

1 ]=> (sqrt 9)

;Aborting!: maximum recursion depth exceeded

解释器抱怨说函数的递归层数太深了,超过了最大的递归深度,它不能处理这样的函数。

问题出在 sqrt-iter 函数,如果使用 trace 来跟踪它的调用过程的话,就会发现它执行了大量的递归调用,这些调用数量非常庞大,最终突破解释器的栈深度,造成错误:

1 ]=> (trace sqrt-iter)

;Unspecified return value

1 ]=> (sqrt 9)

; ...

[Entering #[compound-procedure 11 sqrt-iter]
    Args: 3.
          9]

[Entering #[compound-procedure 11 sqrt-iter]
    Args: 3.
          9]

[Entering #[compound-procedure 11 sqrt-iter]
    Args: 3.
          9]

; ...

[Entering #[compound-procedure 11 sqrt-iter]
    Args: 3.
          9]
^Z
[1]+  已停止               mit-scheme

至于造成 sqrt-iter 函数出错的原因,毫无疑问就是新定义的 new-if 了。

根据书本 12 页所说, if 语句是一种特殊形式,当它的 predicate 部分为真时, then-clause 分支会被求值,否则的话, else-clause 分支被求值,两个 clause 只有一个会被求值。

而另一方面,新定义的 new-if 只是一个普通函数,它没有 if 所具有的特殊形式,根据解释器所使用的应用序求值规则,每个函数的实际参数在传入的时候都会被求值,因此,当使用 new-if 函数时,无论 predicate 是真还是假, then-clauseelse-clause 两个分支都会被求值。

可以用一个很简单的实验验证 ifnew-if 之间的差别,如果使用 if 的话,那么以下的代码只会打印 good :

1 ]=> (if #t (display "good") (display "bad"))
good
;Unspecified return value

如果使用 new-if 的话,那么两个语句都会被打印:

1 ]=> (new-if #t (display "good") (display "bad"))
badgood
;Unspecified return value

这就说明了为什么用 new-if 重定义的 sqrt-iter 会出错:因为无论测试结果如何, sqrt-iter 都会一直递归下去。

当然,单纯的尾递归并不会造成解释器的栈溢出,因为 scheme 解释器的实现都是带有尾递归优化的,但是在 new-if 的这个例子里,因为 sqrt-iter 函数的返回值要被 new-if 作为参数使用,所以对 sqrt-iter 的调用并不是尾递归,这样的话,尾递归优化自然也无法进行了,因此 new-ifsqrt-iter 的递归会最终突破解释器的最大递归深度,从而造成错误:

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)          ; <- sqrt-iter 的返回值还要作为 new-if 的参数,因此 sqrt-iter 的调用不是尾递归
            guess
            (sqrt-iter (improve guess x)    ; <- 无论 good-enough? 的结果如何
                       x)))                 ;    这个函数调用都会被一直执行下去

Note

你可能对 new-if 的输出感到疑惑,为什么 “bad” 会在 “good” 之前输出?事实是,函数式编程语言的解释器实现一般对参数的求值顺序并没有特定的规则,从左向右求值或从右向左求值都是可能的,而这里所使用的 MIT Scheme 使用从右往左的规则,仅此而已,使用不同的 Scheme 实现,打印的结果可能不同。

讨论

blog comments powered by Disqus