sicp习题试解 (1.41) - 王朝网络宽屏版

; ======================================================================

;

; Structure and Interpretation of Computer Programs

; (trial answer to excercises)

;

; 计算机程序的构造和解释(习题试解)

;

; created: code17 03/06/05

; modified:

; (保持内容完整不变前提下，可以任意转载)

; ======================================================================

;; SICP No.1.41

(define (double g) (lambda (x) (g (g x))))

;; Test-it:

;; > (define (inc x) (+ x 1))

;; > ((double inc) 5)

;; 7

;; > (((double (double double)) inc) 5)

;; 21

;; 分析：

;; (double g)的结果是一个两次作用g的函数x|->(g (g x))

;; (double double)的结果是一个两次作用double的函数x|->(double (double x))

;; (double (double double))的结果是一个两次作用(double double)的函数

;; 即x|->((double double) ((double double) x))

;; 则((double (double double)) inc)

;; = ((double double) ((double double) inc))

;; = ((double double) (double (double inc)))

;; = (double (double (double (double inc)))) (*)

;; 因为(double g)的结果是将g作用两次的函数，那么每多一层double，都是将内层

;; 的函数作用变成2倍，则

;; (double inc) = x|-> inc (inc x))

;; (double (double (double (double inc)))) = x |-> (inc (inc (inc ..(inc x)))

;; 共2^4=16次inc

;; 所以(((double (double double)) inc) 5) = (inc (inc (inc...(inc 5))))

;; = 5+1+1+1+.....+1

;; = 21

;; (*) 注意：星号这里，我们将(double (double inc))作为整体代入，实际上是使用

;; 了normal-order evaluation的规则，如果用applicative-order，表达式将比较繁

;; 复(x|->(inc (inc (inc (inc x)))))，尤其是它与前面的部分再结合以后。

;; 所幸的是在本题中这两种order都是终止的，有完全相同的结果。或者，我们可以将这里

;; 的(double (double inc))看作为其自身的evaluation的结果。

;; 证明：

;; 设(f^n x)为(f(f(f...(f x))))的缩写(共n次作用f)

;;

;; 则(double g) = x |-> (g^2 x) ..................................(1)

;; 则(double (x|->(f^n x)))

;; = x |-> ((x|->(f^n x)) ((x|->(f^n x)) x))

;; = x |-> ((x|->(f^n x) (f^n x))

;; = x |-> (f^n (f^n x))

;; = x |-> (f^2n x) ..........................................(2)

;; 则(double^k (x|->f^n x)) = x |-> (f^(n*2^k) x) .................(3)

;;

;; 所以(double double) = x |-> (double^2 x) ................... 由(1)

;; 所以(double (double double))

;; = (double (x|->double^2 x))

;; = (x |-> double^4 x) ......................................由(2)

;; 所以((double (double double)) inc) = (double^4 inc)

;; 而 (double^4 inc)

;; = (double^4 (x |-> (inc^1 x)))

;; = x |-> (inc^(1*2^4) x) .......................................由(3)

;; = x |-> (inc^16 x)

;; 最后，(((double (double double)) inc) 5)

;; = ((x |-> (inc^16 x)) 5)

;; = (inc^16 5)

;; = 21