; ======================================================================
;
; 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
本文地址：http://com.8s8s.com/it/it23029.htm