计算机程序的构造和解释
时光荏苒,程序生涯已度两年余。但构造程序的能力却不尽人意,遂迫切需要获取到构造程序的思维知识,以解目前堆积木式的开发方式的困境。看到书本中间有这么一句话"我们现在的情况就像是在学下象棋的过程中的一个阶段,此时已经知道了移动棋子的各种规则,但却还不知道典型的开局、战术和策略。",这句话非常切近目前的状态。
构造过程抽象
关于抽象的几点表象(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
()))