作者：未知 来源：月光软件站 加入时间：2005-5-13　月光软件站

; ======================================================================
;
;          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:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (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

相关软件：