ch01 构造过程抽象 part01
在计算过程中，Lisp描述（称为过程）本身又可以作为Lisp的数据来表示和操作。
程序设计基本元素
表达式（Expressions）
解释器（interpreter）处理表达式，并显示求值结果（The result of its evaluating the expression）。
值表达式：
486
组合式（Combinations）
组合式的例子：
(+ 137 349) ;Value 486 (- 1000 334) ;Value 666
- 由一对括号形成一个列表（list）。
-
基本过程表达式（可以理解为操作或函数，如
+、-）把值表达式组合起来。 - 前缀表示（prefix notation）：列表中的第一个元素是运算符，其他的是运算对象 （operands）。
前缀表示的优点：
- 适用于可能带任意多个实参的过程
- 可以多层嵌套（nested）
命名和环境
define操作：在全局环境（global environment）定义变量：
(define size 2)
组合式的求值
组合表达式求值的过程就是：先对表达式中最内层求值，然后一层层退到外层。
求值包括两种情况：
-
普通情况：把值代入变量，如
(+ a b)把变量a与b的值代入操作+。 -
特殊形式：如
(define a 1)不是把一个值代入变量a，而是把1赋值给变量a。
Scheme的特点就是特殊形式比较少，绝大多数的求值都是普通情况。
复合过程（Compound Procedures）
定义一个过程(procedure definitions)的格式：
(define (<name> <formal parameters>) <body>)
定义的过程可以用来定义新的过程。例如：
(define (squrae x) (* x x)) // 调用乘法 (define (sum-of-squares x y) (+ (square x) (square y))) // 调用square (define (f a) (sum-of-squares (+ a 1) (* a 2))) // 调用sum-of-squares
过程代换模型
代换模型（Subtitution Model）只是为了帮助理解过程调用如何「归约」与「展开」， 并不是解释器实际工作的描述。
归约（reductions）就是先求出参数的值：
(define (squrae x) (* x x)) ;; 定义过程 square (square (+ 3 2)) ;; 调用过程 square (square 5) ;; 归约（
展开（expansions）就是把参数表达式代入操作：
(define (squrae x) (* x x)) ;; 定义过程 square (square (+ 3 2)) ;; 调用过程 square (* (+ 3 2) (+ 3 2)) ;; 展开
应用序与正则序
以下面三个相互调用的函数为例子：
(define (squrae x) (* x x)) ;; 定义 (define (sum-of-squares x y) (+ (square x) (square y))) ;; 定义 (define (f a) (sum-of-squares (+ a 1) (* a 2))) ;; 定义 (f 5) ;; 当调用时
应用序（application order）：最内层的参数是否为表达式，如果是就先归约。例：
(f 5) ;; 展开为： (sum-of-squares (+ 5 1) (* 5 2)) ;; 归约为： (sum-of-squares 6 10) ;; 展开为： (+ (square 6) (square 10)) ;; 展开为： (+ (* 6 6) (* 10 10)) ;; 归约为： (+ 36 100) ;; 展开为： 136
正则序（normal order）：不求参数表达式的值，把参数表达式代入展开。
(f 5) ;; 展开为： (sum-of-squares (+ 5 1) (* 5 2)) ;; 展开为： (+ (square (+ 5 1)) (square (* 5 2))) ;; 展开为： (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2))) ;; 全部展开了，开始归约为： (+ (* 6 6 ) (* 10 10)) ;; 归约为： (+ 36 100) ;; 归约为： 136
应用序与正则序的差异：
- 对于可以通过替换去模拟，并能产出合法值的过程，应用序和正则序的结果相同。
- 如果结果中有「非法的值」，那二者给出的结果不同。
- 应用序可以避免对表达式的重复求值。（Lisp采用应用序）
- 在超出了可以采用替换方式模拟的过程范围后，正则序更加复杂。
条件表达式和谓词
谓词
谓词（Predicates）：结果为「真」或「假」的表达式。
逻辑运算符
逻辑与：
(and <e1> <e2> ... <en)
逻辑或：
(or <e1> <e2> ... <en)
逻辑非：
(not <e>)
and和or是特殊形式而不普通过程，它们的子表达式不一定都求值（逻辑运算短路）。
not是一个普通的过程。
条件表达式：cond
条件表达式（Conditional Expressions）的标示符为cond：
(cond (<p-1> <e-1>) (<p-2> <e-2>) ... (<p-n> <e-n>) (else <other>) )
例如，：
求绝对值，不用else的版本：
(define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x))))
求绝对值，使用else的版本：
(define (abs x) (cond ((< x 0) (- x)) (else x)))
条件表达式：if
条件表达式格式if格式：
(if <predicate> <consequent> <alternative>)
例：
(define (abs x) (if (< x 0) (- x) x))
练习 1.1
10 ;Value: 10
(+ 5 3 4 ) ;Value: 12
(- 9 1) ;Value: 8
(/ 6 2) ;Value: 3
(+ (* 2 4) (- 4 6)) ;Value: 6
(define a 3) ;Value: a
(define b (+ a 1)) ;Value: b
(+ a b (* a b)) ;Value: 19
(- a b) ;Value: -1
(= a b) ;Value: #f
(if (and (> b a) (< b (* a b)))
b
a) ;Value: 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25)) ;Value: 16
(+ 2 (if (> b a) b a)) ;Value: 6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1)) ;Value: 16
练习 1.2
把以下表示式从中序表达式转换成前序表达式。
\[ \frac{5 + 4 + \left(2 - \left(3 - (6 + \frac{4}{5})\right)\right)} {3(6 - 2)(2 - 7)} \]答：
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7))) ;Value: -37/150
练习 1.3
这道练习的翻译有误，应该是「返回其中较大的两个数的平方和」，而不是 「。。。两个数之和」
定义一个过程，从三个参数中返回两个较大数的平方和。
两个数的平方和：
(define (sum-of-squares x y)
(+ (square x) (square y)))
然后：
(define (bigger-sum-of-squares a b c) ( if (> a b) (if (> b c) (sum-of-squares a b) (sum-of-squares a c)) (if (> a c) (sum-of-squares a b) (sum-of-squares b c)))) (bigger-sum-of-squares 1 2 3) ;Value: 13
另一种解法：
(define (bigger x y) (if (> x y) x y))
(define (smaller x y) (if (> x y) y x))
(define bigger (bigger x y))
(define another-bigger (bigger (smaller x y) z))
;;; 3-bigger-sum-of-squares.scm
(define (bigger-sum-of-squares x y z)
(sum-of-squares (bigger x y) ; bigger
(bigger (smaller x y) z))) ; another bigger
(bigger-sum-of-squares 0 2 2) ; 2^2 + 2^2 = 4 + 4 = 8
(bigger-sum-of-squares 1 2 3) ; 2^2 + 3^2 = 4 + 9 = 13
(bigger-sum-of-squares 3 5 7) ; 5^2 + 7^2 = 25 + 49 = 74
练习 1.4：把函数作为参数
描述下面过程的行为：
;;; 4-a-plus-abs-b.scm
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
函数a-plus-abs-b是第一个展示高阶函数的例子。
在if的判断部分，它根据b的值决定是返回+函数还是-函数，当b大于0时，
它返回+函数：
1 ]=> (if (> 1 0) + -) ;Value 11: #[arity-dispatched-procedure 11] 1 ]=> + ;Value 11: #[arity-dispatched-procedure 11]
当b不大于0时，它返回-函数：
1 ]=> (if (> -1 0) + -) ;Value 12: #[arity-dispatched-procedure 12] 1 ]=> - ;Value 12: #[arity-dispatched-procedure 12] 1 ]=> (load "4-a-plus-abs-b.scm") 1 ]=> (a-plus-abs-b 2 (- 2)) ;Value: 4 1 ]=> (a-plus-abs-b 2 2) ;Value: 4
这种「将函数作为值来传递」是高阶函数能力的一部分，但这还只是开始，后面我们还会 看见更多这方面的应用。
Note
在一些语言中，+和-都是具有特殊作用的运算符（operator），但是在scheme（和许多
其他函数式语言）中，它们只是函数。
练习 1.5：应用序与正则序
下面的语句为什么可以判断是应用序还是正则序：
(define (p) (p)) (define (test x y) (if (= x 0) 0 y)) (test 0 (p))
首先，可以确定的是，无论解释器使用的是什么求值方式，调用(p)总是进入一个
无限循环(infinite loop)，因为函数p会不断调用自身：
(define (p) (p))
具体到解释器中，执行(p)调用会让解释器陷入停滞，最后只能强制将解释器进程杀掉：
1 ]=> (p) ^Z [1]+ 已停止 mit-scheme $ killall mit-scheme
在应用序中，所有被传入的实际参数都会立即被求值，因此，在使用应用序的解释器里
执行(test 0 (p))时，实际参数0和(p)都会被求值，而对(p)的求值将使解释器
进入无限循环，因此，如果一个解释器在运行Ben的测试时陷入停滞，那么这个解释器
使用的是应用序求值模式。
另一方面，在正则序中，传入的实际参数只有在有需要时才会被求值，因此，在使用
正则序的解释器里运行(test 0 (p))时，0和(p)都不会立即被求值，当解释进行到
if语句时，形式参数x的实际参数(也即是0)会被求值(求值结果也是为0)，然后和
另一个0进行对比((= x 0))，因为对比的值为真(#t),所以 if返回0作为值表达式
的值，而这个值又作为test函数的值被返回。
因为在正则序求值中，调用(p)从始到终都没有被执行，所以也就不会产生无限循环，
因此，如果一个解释器在运行 Ben 的测试时顺利返回0，那么这个解释器使用的是
正则序求值模式。
Note
另一个需要说明的地方是「形式参数」和「实际参数」两个名词。
对于一个函数来说，它接受的参数的局部名被称为形式参数。
而调用函数时传入的表达式，被称为实际参数。
比如说，对于函数(define (square x) (* x x))来说，x就是形式参数，当进行调用
(square 2)时，2就是形式参数x的实际参数。
当人们只说「参数」而不说明它是「形式参数」还是「实际参数」时，他们一般指的是 「形式参数」，但是具体还是要看上下文来决定。
牛顿方法求平方根
数学上的定义角度为「是什么」。比如对于平方根的定义：
\[ \begin{equation} \sqrt[2]{x} = y, \quad \text{使得$y \geq 0$ 而且 $y^2 = x$} \end{equation} \]算法上的定义角度为「怎么做」。比如牛顿解法：
随便找一个比x小的数字y，算出\(y\)与\(x/y\)的平均值：
结果就是近舍入值，如果要更加精确，就把结果作为新的y重复以上步骤。
代码实现：
(define (average x y) ; 求平均值的方法
(/ (+ x y) 2))
(define (improve guess x) ; 猜测数与x的平均值
(average guess (/ x guess)))
(define (good-enough? guess x) ; 定义精度0.001满足要求
(< (abs (- (square guess) x)) 0.001))
(define (sqrt-iter guess x) ; 主方法
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (sqrt x) (sqrt-iter 1.0 x))
(sqrt 9) ;Value: 3.00009155413138
(sqrt (+ 100 37)) ;Value: 11.704699917758145
(sqrt (+ (sqrt 2) (sqrt 3))) ;Value: 1.7739279023207892
(square (sqrt 1000)) ;Value: 1000.000369924366
练习 1.6
if不是一个普通的过程，是一个特殊处理。能不能不要这个例外处理，直接用cond
实现一个新版本的if：
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
可以进行逻辑处理：
(new-if (= 2 3) 0 5) (new-if (= 1 1) 0 5)
但使用开方运算时，发现调用层数超过限制：
;; new sqrt by new if
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt 9) ;Aborting!: maximum recursion depth exceeded
(sqrt (+ 100 37)) ;Aborting!: maximum recursion depth exceeded
(sqrt (+ (sqrt 2) (sqrt 3))) ;Aborting!: maximum recursion depth exceeded
(square (sqrt 1000)) ;Aborting!: maximum recursion depth exceeded
if语句的短路特性
根据书本 12 页所说， if 语句是一种特殊形式，当它的predicate部分为真时，
then-clause分支会被求值，否则的话，else-clause分支被求值，两个clause只有
一个会被求值。
而另一方面，新定义的new-if只是一个普通函数，它没有if所具有的特殊形式，
根据解释器所使用的应用序求值规则，每个函数的实际参数在传入的时候都会被求值，
因此，当使用new-if函数时，无论predicate是真还是假，then-clause和
else-clause两个分支都会被求值。
无论测试结果如何，sqrt-iter都会一直递归下去。
如果使用trace来跟踪sqrt-iter的调用过程的话，就会发现它执行了大量的递归调用
，这些调用数量非常庞大，最终突破解释器的栈深度，造成错误：
1 ]=> (trace sqrt-iter)
;Unspecified return value
1 ]=> (sqrt 9)
; ...
[Entering #[compound-procedure 11 sqrt-iter]
Args: 3.
9]
[Entering #[compound-procedure 11 sqrt-iter]
Args: 3.
9]
[Entering #[compound-procedure 11 sqrt-iter]
Args: 3.
9]
; ...
[Entering #[compound-procedure 11 sqrt-iter]
Args: 3.
9]
^Z
[1]+ 已停止 mit-scheme
参数求值顺序从右到左
注意：
事实是，函数式编程语言的解释器实现一般对参数的求值顺序并没有特定的规则， 从左向右求值或从右向左求值都是可能的，而这里所使用的MIT Scheme使用从右往左的 规则，仅此而已，使用不同的 Scheme 实现，打印的结果可能不同。
当然，单纯的尾递归并不会造成解释器的栈溢出，因为 scheme 解释器的实现都是带有
尾递归优化的，但是在new-if的这个例子里，因为sqrt-iter函数的返回值要被
new-if作为参数使用，所以对sqrt-iter的调用并不是尾递归，这样的话，尾递归优化
自然也无法进行了，因此new-if和sqrt-iter的递归会最终突破解释器的最大递归深度
，从而造成错误
(define (sqrt-iter guess x) (new-if (good-enough? guess x) ; <- sqrt-iter 的返回值还要作为 new-if 的参数 guess ; ，因此 sqrt-iter 的调用不是尾递归 (sqrt-iter (improve guess x) ; <- 无论 good-enough? 的结果如何 x))) ; 这个函数调用都会被一直执行下去
练习 1.7：修复精度问题
先将书本 16 页的 sqrt 函数完整敲下来：
;;; p16-sqrt.scm
(load "p15-sqrt-iter.scm")
(define (sqrt x)
(sqrt-iter 1.0 x))
然后使用 sqrt 函数进行实验测试：
1 ]=> (load "p16-sqrt.scm") ;Loading "p16-sqrt.scm"... ; Loading "p15-sqrt-iter.scm"... ; Loading "p15-good-enough.scm"... done ; Loading "p15-improve.scm"... ; Loading "p15-average.scm"... done ; ... done ; ... done ;... done ;Value: sqrt 1 ]=> (sqrt 0.00009) ; 正确答案应该是 9.486832980505138e-3 ;Value: .03220324381282134 ; 死循环 1 ]=> (sqrt 90000000000000000000000000000000000000000000000000000000000000) ^C
可以发现，对于特别小的数，比如0.00009，书本给出的sqrt并不能计算出正确的答案
； 而对于特别大的数，因为mit-scheme实现的小数精度不足以表示两个大数之间的差，
所以sqrt会陷入死循环而无法得出正确结果。
要避免这一错误，我们按照练习所说，对good-enough?进行修改：不再检测猜测值
guess的平方与x之间的差，而是检测新旧两次猜测值之间的比率，当比率变化非常小
时，程序就停止improve。
新的good-enough?定义如下：
;;; 7-good-enough.scm
(define (good-enough? old-guess new-guess)
(> 0.01
(/ (abs (- new-guess old-guess))
old-guess)))
使用新的good-enough?重新定义sqrt函数 —— 大部分的代码和原来的一样，只是
sqrt-iter和good-enough?两个函数更改了：
;;; 7-sqrt.scm
(load "p16-sqrt.scm") ; 一定要先载入这些函数
(load "p15-improve.scm") ; 确保后面定义的重名函数可以覆盖它们
(load "p15-average.scm")
(load "7-good-enough.scm") ; 载入新的 good-enough?
(define (sqrt-iter guess x)
(if (good-enough? guess (improve guess x)) ; 调用新的 good-enough?
(improve guess x)
(sqrt-iter (improve guess x)
x)))
新的sqrt函数对于非常小和非常大的值都能给出正确答案：
1 ]=> (load "7-sqrt.scm") ;Loading "7-sqrt.scm"... ; Loading "p16-sqrt.scm"... ; Loading "p15-sqrt-iter.scm"... ; Loading "p15-good-enough.scm"... done ; Loading "p15-improve.scm"... ; Loading "p15-average.scm"... done ; ... done ; ... done ; ... done ; Loading "p15-improve.scm"... ; Loading "p15-average.scm"... done ; ... done ; Loading "p15-average.scm"... done ; Loading "7-good-enough.scm"... done ;... done ;Value: sqrt-iter 1 ]=> (sqrt 0.00009) ;Value: 9.486833049684392e-3 1 ]=> (sqrt 900000000000000000000000000000000000000000000000000000000000000) ;Value: 9.486982144406554e41
注意：
在新的sqrt-iter的定义中，(improve guess x)被重复调用了多次，这是因为书本到
这个练习为止还没有介绍let结构。
以下是一个使用let结构重写的、无重复调用的sqrt-iter：
(define (sqrt-iter old-guess x)
(let ((new-guess (improve old-guess x)))
(if (good-enough? old-guess new-guess)
new-guess
(sqrt-iter new-guess x))))
练习 1.8：牛顿立方根公式
如果y是x立方根的一个近似值，那么下面的公式可以得到一个更好的近似值：
首先，将题目给定的算式转换成前序表达式：
(/ (+ (/ x (square y)) (* 2 y)) 3)
然后将这个表达式应用到improve函数，再修改一下sqrt函数(书本 15 页)，就可以
得出计算三次方根的函数cube-root：
;;; 8-cube-root.scm
(load "8-cube.scm")
(define (cube-root x)
(cube-root-iter 1.0 x))
(define (cube-root-iter guess x) ; 和 sqrt-iter 是一样的
(if (good-enough? guess x) ; 改个名字，方便区别
guess
(cube-root-iter (improve guess x) x)))
(define (good-enough? guess x) ; 要用 cube 来检测是否足够好
(< (abs (- (cube guess) x)) 0.001))
(define (improve guess x) ; 题目给出的公式
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
要注意cube-root和sqrt两个函数之间的细微区别，小心别把它们混淆了。
因为 MIT Scheme 里没有计算立方的cube函数，所以需要自己写一个：
;;; 8-cube.scm (define (cube x) (* x x x))
最后，测试cube-root函数：
1 ]=> (load "8-cube-root.scm") ;Loading "8-cube-root.scm"... ; Loading "8-cube.scm"... done ;... done ;Value: improve 1 ]=> (cube-root (* 3 3 3)) ;Value: 3.0000005410641766 1 ]=> (cube-root (* 5 5 5)) ;Value: 5.000000000287929 1 ]=> (cube-root (* 7 7 7)) ;Value: 7.000001795382107
过程作为黑箱抽象
关心过程的作用，而忽略过程的实现。
局部名
- 约束变量（bound variable）：限制变量的有效范围。
- 作用域（scope）：被约束的变量的有效范围。
- 自由变量：不被约束的变量。
例子：过程的定义就约束了它所有的形式参数。
内部定义与块结构
不仅是变量，过程也可以被限制在作用域内。
例：虽然sqrt过程依赖其他的三个过程，但不应该把那三个过程暴露出来：
(define (average x y) ; 求平均值的方法
(/ (+ x y) 2))
(define (improve guess x) ; 猜测数与x的平均值
(average guess (/ x guess)))
(define (good-enough? guess x) ; 定义精度0.001满足要求
(< (abs (- (square guess) x)) 0.001))
(define (sqrt-iter guess x) ; 主方法
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (sqrt x) (sqrt-iter 1.0 x))
块结构（block structure）把子过程都定义为局部的成员。这样其他的过程可以 有自己的同名子过程而不会相互冲突：
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))
词法作用域（lexical scoping）：当前过程内的自由变量其实是外部作用域的一个绑定
变量。比如上面sqrt过程的参数x可以被内部的过程直接访问，不用在三个过程中
传来传去：
(define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))