计算机程序的构造和解释
Table of Contents
时光荏苒，程序生涯已度两年余。但构造程序的能力却不尽人意，遂迫切需要获取到构造程序的思维知识，以解目前堆积木式的开发方式的困境。看到书本中间有这么一句话"我们现在的情况就像是在学下象棋的过程中的一个阶段，此时已经知道了移动棋子的各种规则，但却还不知道典型的开局、战术和策略。"，这句话非常切近目前的状态。
构造过程抽象
关于抽象的几点表象（John Locke - 有关人类理解的随笔.1690）：
- 将若干简单认知组合为一个复合认知，由此产生各种复杂的认知。
- 将两个认知放在一起对照。不管它们如何简单或复杂，并不将它们合而为一。由此得到有关它们相互关系的认知。
- 将有关知识跟那些在实际中和它们同在的所有其他人知隔离开。
计算过程、数据抽象和程序
"计算过程"是存在于计算机中的一类抽象事物，这些过程会去操作一些被称为"数据"的抽象事物。人们创建出一些称为"程序"的规则模式，以指导这类过程的进行。程序用一些程序设计语言，通过"符号表达式"的形式精心编排而成，它描述了希望相应的计算过程去完成的工作。
设计良好的计算系统应具有某种模块化设计，其中各部分都可以独立的构造、替换、排除错误。
关于Lisp的介绍
Lisp的名字来自表处理（LISt Processing），于20世纪50年代后期由John McCarthy基于他的论文“Recursive Functions of Symbolic Expressions and Their Computation by Machine”（符号表达式的递归函数及其机械计算 1960）发明。
强有力的程序设计语言，不仅是一种指挥计算机执行任务的方式，还应该成为一种框架，使我们能够在其中组织自己有关计算过程的思想。在描述一个语言时，需要将注意力特别放在语言所提供的，能够将简单认知组合起来形成更复杂认知的方法方面。每一种强有力的语言都为此提供了三种机制：
- 基本表达式 - 用于表达语言所关心的最简单的个体
- 组合的方法 - 通过它们可以从较简单的东西出发构造出复合的元素
- 抽象的方法 - 通过他们可以为复合对象命名，并将它们当作单元去操作
程序设计中需要处理的两类要素
- 过程 - 有关操作数据的规则的描述
- 数据 - 我们希望去操作的"东西"
复合表达式 、组合式具体定义是什么？
求值环境 - 存储、维护、保持值与符号的关联
基本过程 - 编程语言提供的一些内置的操作过程（Lisp中的特殊形式 + - define）EXP：(+ 2 3) (define x 2)
复合过程 - 将基本过程组合起来的自定义过程 EXP: (define (square x) (* x x))
过程求值的两种模型：
- 应用序解释器首先对运算符和各个运算对象求值，而后将得到的过程应用于得到的实际参数。这种"先求值参数而后应用"的求值模型称为"应用序求值"
- 正则序解释器先不求出运算对象的值，直到需要它们的值时再做。首先用运算对象表达式去替换形式参数，直至得到一个只包含基本运算符的表达式，然后再去执行求值。这种"完全展开而后归约"的求值模型称为"正则序求值"
练习1.1
MIT/GNU Scheme running under OS X Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2014 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Wednesday January 4, 2017 at 8:46:32 AM Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116 1 ]=> 10 ;Value: 10 1 ]=> (+ 5 3 4) ;Value: 12 1 ]=> (- 9 1) ;Value: 8 1 ]=> (/ 6 2) ;Value: 3 1 ]=> (+ (* 2 4) (- 4 6)) ;Value: 6 1 ]=> (define a 3) ;Value: a 1 ]=> (define b (+ a 1)) ;Value: b 1 ]=> (+ a b (* a b)) ;Value: 19 1 ]=> (= a b) ;Value: #f 1 ]=> (if (and (> b a) (< b (* a b))) b a) ;Value: 4 1 ]=> (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) ;Value: 16 1 ]=> (+ 2 (if (> b a) b a)) ;Value: 6 1 ]=> (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) ;Value: 16
练习1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))练习1.3 - 定义一个过程，它以三个数位参数，返回其中较大两个数之和
;;; 求三个数字中较大的两个之和
(define (sum-tow-large-num number-1 number-2 number-3)
(- (+ number-1 number-2 number-3) (fetch-small number-1 number-2 number-3)))
;;; 求三个数字中较小的数字
;;; 最小值的决策树
;;; (x < y)
;;; (x < z) (y < z)
;;; (x < y x < z) (x < y z < x) (y < x y < z) (y < x z < y)
(define (fetch-small number-1 number-2 number-3)
(cond
((and (< number-1 number-2) (< number-1 number-3)) number-1)
((and (< number-1 number-2) (< number-3 number-1)) number-3)
((and (< number-2 number-1) (< number-2 number-3)) number-2)
((and (< number-2 number-1) (< number-3 number-2)) number-3)))练习1.4 - 考察允许运算符为复合表达式的组合式的求值模型，根据这一模型的认知描述下面过程的行为
(define (a-plush-abs-b a b)
((if (> b 0) + -) a b))首先允许运算法为符合表达式的组合式。根据Lisp求值原则首先求值(if (> b 0) + -)表达式，将a、b值作用于其结果 + 或 - 符号。得（+/- a b)。
MIT/GNU Scheme running under OS X Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2014 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Wednesday January 4, 2017 at 8:46:32 AM Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116 1 ]=> (define a 10) ;Value: a 1 ]=> (define b 20) ;Value: b 1 ]=> (define sybol (if (> b 0) + -)) ;Value: sybol 1 ]=> (sybol a b) ;Value: 30 1 ]=>
练习1.5 - Ben Bitdiddle 发明了一种检测方法，能够确定解释器究竟使用哪种序求值，是采用应用序，还是采用正则序。他定义了两个过程：
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))而后他求值下面的表达式：
(test 0 (p))如果某个解释器采用的是应用序求值，Ben会看到什么样的情况？如果解释器采用的是正则序求值，他又会看到什么情况？请对你的回答作出解释。（无论采用正则序或者应用序，假定特殊形式if的求值规则总是一样的。其中谓词部分先行求值，根据其结果确定随后求值的子表达式部分）。
应用序求值：求值结果是程序陷入无限自身调用。在应用序求值（test 0 (p)) 时，从左向右求值依次时test、0、(p)。test已在全局环境中绑定，数字0求值结果为其自身，因为过程p返回的是其自身，(p)求值时陷入无限循环（调用自身）。
正则序求值：求值结果是0。在正则序求值时(test 0 (p))时，根据其求值规则'解释器先不求值运算对象'，将过程test展开(if (= x 0) 0 y) 并求值返回0，if形式又是test的最后、唯一一个形式，所以test过程的求值结果为0
牛顿法求平方根
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x))
;;; BUG‘s Code
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))练习1.6
程序运行结果
1 ]=> (define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
;Value: new-if
1 ]=> (define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
;Value: sqrt-iter
1 ]=> (sqrt 2)
;Aborting!: maximum recursion depth exceeded
解释 - 根据应用序求值规则判断'new-if'在调用时，其形式参数总是被求值，同时sqrt-iter并非尾递归调用。也就是说'(sqrt-iter (improve guess x) x)'表达式总被调用求值，从而导致"超过最大递归深度"(maximum recursion depth exceeded)问题。而if特殊形式在条件表达式求值为false时，其else部分不被求值。
练习1.7
(define (sqrt x)
(sqrt-iter 1.0 x))
(define (sqrt-iter guess x)
(if (new-good-enough guess (improve guess x))
(improve guess x)
(sqrt-iter (improve guess x) x)))
(define (improve guess x)
(adv guess (/ x guess)))
(define (adv x y)
(/ (+ x y) 2))
(define (good-enough guess x)
(< (abs (- (square guess) x)) 0.001))
(define (new-good-enough old-guess new-guess)
(> 0.01 (/ (abs (- new-guess old-guess)) old-guess)))练习1.8
(define (sqrt x)
(sqrt-iter-3 1.0 x))
(define (sqrt-iter-3 guess x)
(if (new-good-enough guess (imp guess x))
(imp guess x)
(sqrt-iter-3 (imp guess x) x)))
(define (new-good-enough old-guess new-guess)
(> 0.01 (/ (abs (- new-guess old-guess)) old-guess)))
(define (imp guess x)
(adv (/ x (square guess)) (* 2 guess)))
(define (adv x y)
(/ (+ x y) 3))过程抽象
- 每个过程应完成一件可以清楚标明的工作，使其可以被用作定义其他过程的模块
- 每个过程应该能隐藏起清楚标明的工作细节，使过程的使用者将其作为一个黑箱使用
- 每个过程的意义应该不依赖于其作者为形式参数所选用的名字
线性的递归和迭代
- 递归计算过程
- 迭代计算过程
- 线性递归过程
- 线性迭代过程
递归计算过程和递归过程
当过程是递归的时候，论述的是语法形式上的事实，说明这个过程的定义中（直接或间接的）引用了该过程本身。在说某一计算过程具有某种模式时（如线性递归）是指这一计算过程的进展方式。应明确区分两者的含义。递归过程产生出迭代计算的例子：
;;; 递归过程产生的迭代计算
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product) (+ counter 1) (max-count))))练习1.9
;;; First
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
;;; Second
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
(+ 4 5)
;;; First
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
(9)
;;; Second
(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8)) (+ 0 9)
(9)两个过程都是递归过程。其中First是递归计算过程、Second是迭代计算过程。
练习1.10
(define (A x y)
(cond
((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))))
;; 求值 (A 1 10) =>>
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
(1024)
;; 求值 (A 2 4) =>>
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
(A 0 (A 1 15))
(A 0 (A 0 (A 1 14)))
(A 0 (A 0 (A 0 (A 1 13))))
(A 0 (A 0 (A 0 (A 0 (A 1 12)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 8192)))
(A 0 (A 0 16384))
(A 0 32768)
(65536)
;; 求值 (A 3 3) =>>
(define (nothing)
(display "I'm tired!"))
(define (f n) (A 0 n)) ; 2n
(define (g n) (A 1 n)) ; 2^n
(define (h n) (A 2 n)) ; 2^2^2... n ...^2
(define (k n) (* 5 n n)) ; 5n^2斐波那契数列
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
(define (fib n)
(fib-iter 0 1 n))
(define (fib-iter a b count)
(if (= count 0) a (fib-iter b (+ a b) (- count 1))))
(fib 5)
(+ (fib 4) (fib 3))
(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))
(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) (fib 1)))
(+ (+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0)) (+ (+ 1 0) 1))
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))
(5)练习1.11
;; Recursion
(define (f n)
(if (< n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
;; iteration
;; f(3)=f(2)+2f(1)+3f(0)
;; f(4)=f(3)+2f(2)+3f(1)
;; f(5)=f(4)+2f(3)+3f(2)
(define (f n)
(f-iter 0 1 2 n))
(define (f-iter a b c n)
(if (< n 3)
a
()))