SICP学习笔记 2.1.3 数据意味着什么

    练习2.4

(define (new-cons x y)
  (lambda (m) (m x y)))
(define (new-car z)
  (z (lambda (p q) p)))
  
;; 使用代换模型，(new-car (new-cons x y))的变换过程如下
(new-car (new-cons x y))
==> (new-car (lambda (m) (m x y)))
==> ((lambda (m) (m x y)) (lambda (p q) p))
==> 此时即为使用过程(lambda (p q) p)去处理(x y)
==> 即等价于定义过程
		(define (test p q) p)
		然后计算
		(test x y)
==> 所以(new-car (new-cons x y))将得到x

;; 由上面的分析, 可以得到
(define (new-car z)
  (z (lambda (p q) q)))

 

    练习2.5

(define (new-cons a b)
  (* (expt 2 a) (expt 3 b)))
(define (cons-iter x k n)
  (if (= (remainder x k) 0)
      (cons-iter (/ x k) k (+ n 1))
      n))
(define (new-car z)
  (cons-iter z 2 0))
(define (new-cdr z)
  (cons-iter z 3 0))

 

    练习2.6

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))
  
;; 由以上定义的过程以及 1 = 0 + 1 可得如下过程
(define one (add-1 zero))

;; 进行代入变换
(add-1 zero)
==> (lambda (f) (lambda (x) (f ((zero f) x))))
==> (lambda (f) (lambda (x) (f ((lambda (x) x) x))))
==> (lambda (f) (lambda (x) (f x)))

;; 则可得如下过程
(define one (lambda (f) (lambda (x) (f x))))

;; 进而得到如下过程
(define two (lambda (f) (lambda (x) (f (f x)))))

;; 采用代入的方式进行验证
(define two (add-1 one))
(add-1 one)
==> (lambda (f) (lambda (x) (f ((one f) x))))
==> (lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
==> (lambda (f) (lambda (x) (f (f x))))

;; 进而得到对于N的定义
(define N (lambda (f) (lambda (x) (f (f ... (f x))))))
;; 则可得到如下过程
(define N (lambda (f) (lambda (x) ((N f) x))))

;; 而对于N+M, 即为对N调用M次add-1
;; 对于N+1
(add-1 N)
==> (lambda (f) (lambda (x) (f ((N f) x))))
==> (lambda (f) (lambda (x) ((one f) ((N f) x))))

(add-1 (N+1))
==> (lambda (f) (lambda (x) ((two f) ((N f) x))))

(add-1 (N+M))
==> (lambda (f) (lambda (x) ((M f) ((N f) x))))

;; 所以推得加法的过程如下
(define (add N M)
  (lambda (f) (lambda (x) ((N f) ((M f) x)))))

;; 确实如书中所说：In case representing pairs as procedures wasn't mind-boggling enough, 
;; consider that ......
;; Alonzo Church真乃神人也！