SICP-CH1-构造过程抽象

1. 构造过程抽象

sicp窝终于回来了…

[前言] 首先总结一下前言吧. 这本书的目标是教授一种通用的方法学思想, 不仅限于计算机程序设计. 采用scheme(lisp的一种方言)教授这门课,是因为它集powerful与beautiful于一身.

ps:第一句话说这本书是MIT计算机科学的入门教材…看到这个我就跪下了.

1 构造过程抽象

计算过程: 存在于计算机里的一类抽象事物,这些过程会去操作一些称为 数据 的抽象事物. 人们创建出一些称为 程序 的规则模式, 以指导这类过程的进行.

计算过程的lisp描述本身可以作为lisp的数据来表示和操作. 这种灵活性使lisp称为探索语言特征的最方便的语言之一.

1.1 程序设计的基本元素

一个powerful的语言, 除了能够执行任务, 更应该能帮助程序猿组织自己的思想.

基本表达形式
组合的方法
抽象的方法

在程序设计中,我们需要处理两类要素:过程和数据. 本章把重点放在过程上.

1.1.1 表达式

最简单的表达式: 42, 表示基本过程的表达式: ( + 42 42 ). '+'称为 运算符, 数字是 运算对象, 求值过程就是将运算符所刻画的运算过程应用于运算对象.

lisp把运算符放在左边, 称为 前缀表示. 前缀表示的优点是:

可以带有任意个实参而没有歧义
可以直接扩充, 允许出现组合式嵌套, 如(+ ( * 3 5 ) ( - 10 6))

1.1.2 命名和环境

程序设计语言需要提供一种[通过名字去使用计算对象]的方式.

在scheme中, 命名通过define来进行.

(define size 2)

我们可以把值2与符号size关联, 又能够提取出这个值, 这说明解释器有存储能力,以维护名字-值对偶的轨迹, 这种存储称为 环境.

1.1.3 组合式求值

求值一个组合式的步骤是:

1) 求值该组合式的各个子表达式
2) 将作为最左子表达式的值的过程应用于相应的实际参数.

没错就是递归. 递归是一种处理层次结构的强有力的技术. 这种计算过程称为 树形积累.

在求值过程中, 环境 用于确定表达式中各个符号的意义, 它为求值过程提供了一种上下文.

例外: 对表达式 (define x 1) 求值不是把define运用于两个参数, 因为define的作用是关联x和1, 也就是说(define x 1)不是一个组合式. 这种例外称为 特殊形式 .

1.1.4 复合过程

上述的某些元素也会出现在其它语言中:

数和算术运算是基本的数据和过程
组合式的嵌套提供了一种组织起多个操作的方法
定义是一种受限的抽象手段, 它为名字关联响应的值.

下面来讲威力更强大的 过程定义

(define (square x) (* x x ))

上面定义了一个复合过程square, 定义好之后可以这样使用

(square 21)

有点像定义函数. 接下来我们可以把square作为基本构建去定义其它过程

(define (sum-of-squares x y) ( + (square x) (square Y)))

复合过程的使用方式与基本过程完全一致.

1.1.5 过程应用的代换模型

对带有复合过程的组合式求值, 解释器会先"展开"复合过程, 把问题规约为对另一个组合式求值.

(square 21) -> (* 21 21)

这种计算过程称为过程应用的 代换模型

应用序: 先求值参数而后应用的求值模型

正则序: 完全展开而后规约的求值模型

lisp采用应用序求值, 部分原因在于这样可以避免对于表达式的重复求值, 重点是在超出可以采用替换方式模拟的过程范围之后, 正则序的处理将变得复杂的多.

1.1.6 条件表达式和谓词

条件表达式依据不同情况采取不同动作的结构叫做 分情况分析 cond

(cond ((> x 0 )x) ((= x 0) 0) ((< x 0) (-x)))
(cond ((< x 0) (-x) (else x)))

else是一个特殊符号,可以用在cond最后一个位置,如果cond所有分支都被跳过,就会返回else的值 if

(if (< x 0) (-x) x)

if是cond的一种受限形式, 适用于只有两种情况的分析. 谓词: < > and or not … 注意and和or都是特殊形式,它们的子表达式不一定求值. not则是一个普通过程.

1.1.7 [习题]

1.1 .求值(选做一部分)

(define a 3) -> a (define b ( + a 1)) -> b (= a b) -> #f

1.2 将下面表达式变换为前缀形式:

(5+4+(2-(3-(6+5/4))))/(3*(6-2)(2-7))

(/ (+ 5 4 (- 2 (- 3 ( + 6 (/ 5 4))))) (* 3 (- 6 2) ( - 2 7)))

1.3 定义一个过程, 它以三个数为参数, 返回其中较大的两个数之和

(define (min x y z) 
      (cond (((< x y) and (< x z))  x)
  (((< y x) and (< y z))  y)
  (else z)))
(define (sum2 x y z) (- (+ x y z) (min x y z )))

1.4 仔细考察上面给出的允许运算符为复合表达式的组合式的求值模型, 根据对这一模型的认知描述下面过程的行为:

(define (a-plus-abs-b a b) ((if (> b 0)  + -) a b))

对子表达式(> b 0)求值, 得结果r1
对子表达式(if (r1) + -)求值, 得到结果r2, r2是运算过程.
对(r2 a b)求值
1.5 Ben发明了一种检测方法,能够确定解释器以正则序求值, 还是以应用序求值. 他定义了下面两个过程:

(define (p) (p))
(define (test x y) (if ( = x 0) 0 y))
(test 0 (p))

用应用序和正则序解释器运行它们, 最终会发生什么?

应用序: 0
正则序: 无限循环. 因为无论(= x 0)的结果如何, y都会被求值.

1.2 实例:采用牛顿法求平方根

上面介绍的过程都很像常规数学函数, 然而数学和计算机过程有一些区别:

数学关心说明性的描述(是什么)
计算机关心行动性的描述(怎么做)

一个求平方根的数学描述是: squrt(x) = y, y>=0 && y²=x. 我们无法把它直译成计算机函数. 计算机求平方根的常用方法是: 牛顿逐步逼近法 : 先猜测一个值a, 并计算b = x/a, 比较a和b是否足够相似, 如果不满足条件则执行一些操作得到更好的猜测a2, 循环往复直到求出平方根.

基本策略:

(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 (squrt x) (sqrt-iter 1.0 x))

1.2.1 [习题]

1.6 可否通过cond定义一个常规过程来代替if呢? Eva尝试写了以下程序,

问: 如果用这个new-if来实现求平方根程序sqrt-iter,会有什么问题

(define (new-if predicate then-clause else-clause)
        (cond (predicate then-clause)
              (else else-clause)))

答: 问题在于cond的所有分支都会被求值. sqrt-iter是递归,if满足条件时不对else-clause求值, 从而可以停止递归调用. 而new-if由于所有分支都会无条件求值, 所以它应用于递归函数时根本停不下来.

1.7 上面good-enough的实现对于很小或很大的数来说不太好, 请给出证明.

如果使用监测猜测值改变比率的方式, 对于大数或小数来说可以工作吗?

对于小于0.001(good-enough的临界值)的小数,good-enough无法进行正确的判断.

对于大数来说, 由于精度不足以表示guess和x之间的差(good-enough几乎永远为false), 程序陷入死循环.

改变比率的算法对大数和小数都可以工作.

(define (good-enough old-guess new-guess)
        (< (/ (abs (- old-guess new-guess)) old-guess) 0.01))

1.8 用牛顿法求立方根

如果y是x立方根的一个近似值,那么下面公式可以给出一个更好的近似值: (x/y² +2*y)/3

(define (cube-iter guess x)
  (if (good-enough-cube guess x)
      guess
      (cube-iter (improve-cube guess x) x)))

(define (good-enough-cube guess x)
        (< (abs (- (* guess guess  guess) x)) 0.001))

(define (improve-cube y x)
    (/ (+ (/ x (* y y)) (* 2 y)) 3))

(define (cube x) (cube-iter 1 x))

1.3 过程作为黑箱抽象

过程抽象 一个过程的定义应当能隐藏起一些细节,使得过程的使用者可以直接复用而不必关心实现细节.

1.3.1 局部名

过程的意义应该不依赖于其作者为形式参数所选定的名字.

一个过程的定义 约束 了它所有形式参数,形参的具体名字完全没有关系, 这样的名字称为 约束变量 . 相反如果一个变量不是被约束的, 它就是 自由的.

1.3.2 内部定义和块结构

平方根程序有个问题, 它由许多分离的过程组成, 而实际用户只关心sqrt这一个过程, 其它过程不必暴露给用户. (要运行这个程序也很蛋疼啊…)

所以,我们需要把这些麻烦的子过程局部化, 把它们隐藏到sqrt里面.

(define (sqrt x)
   (define (good-enough ...))
   (define (improve-guess ...))
   (if (good-enough ...) ...)) ;;懒得敲了,自行脑补吧...

这种嵌套的定义称为 块结构. 它是最简单的名字包装问题的一种正确解决方式. (讲道理这话真的是绕…

另外, 采用这种结构除了可以把辅助过程隐藏之外, 还可以利用 词法作用域 来简化辅助过程的形参. 对这个例子来说,可以省略掉许多x.

[小历史] 块结构的思想来自程序设计语言Algol 60.

1.4 过程与它们所产生的计算

能够看清所考虑的动作的后果的能力, 是非常重要的. 只有在此之后, 人们才能 反向推理

1.4.1 线性的递归和迭代

两种计算过程: 线性递归过程 在这种计算过程里,代换模型展示出一种先展开后收缩的形状,最大长度正比于n. 解释器为递归过程维护一部分状态信息.递归过程所消耗的内存与n成正比. 注意[递归计算过程]与[递归过程]是两个概念. 迭代计算过程 可以用固定数目的状态描述的计算过程. 与递归不同的是, 迭代计算过程中不会出现增长或收缩. 迭代过程的所有状态信息都保存在程序遍历昂立.迭代过程所消耗的内存是固定的.

某些语言(Pascal,C..)对递归过程的解释,消耗的内存总是与n成正比, 即使所描述的计算过程是迭代的. 要描述迭代过程, 必须借助于"循环结构".而scheme则没有这个缺陷. 尾递归 总是能在常量的空间中执行迭代型计算过程.

1.4.2 [习题]

1.9 用代换模型展示下面两个过程在求值(+ 4 5)时所产生的计算过程. 它们是递归或者迭代吗?

(define (+ a b) (if (= a 0) b (inc (+ (dec a) b))))

计算过程(纯手打):

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

它是递归计算过程

(define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))

计算过程:

(+ 4 5)
(+ 3 7)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

它是迭代计算过程

下面是一个称为ackermann函数的数学函数
(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) 1024
- (A 2 4) 65536
(a 1 (a 2 3)).. (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 (* 2 2))),(a 1(a 1 4)),(a 1 16),2¹⁶
- (A 3 3) 65536
(a 2 (a 3 2)),(a 2(a 2(a 3 1))),(a 2 (a 2 2)),(a 2 4),65536

下面过程的数学定义是?
- (define (f n) (A 0 n)) : f = 2*n
- (define (g n) (A 1 n)) : g = 2ⁿ
- (define (h n) (A 2 n)) : h = 2^(2^(2…)

1.4.3 树形递归

另一种常见的例子🌰,比如菲波那切数列.

朴素的树形递归:

(define (fib n)
 (cond ((= n 0) 0)
  ((= n 1) 1)
  (else (+ (fib (- n 1)) (fib ( - n 2))))))

优化的迭代版本:

(define (fib-it a b count)
(cond ((= count 0) b)
  (else (fib-it (+ a b) a (- count 1)))))
(define (fib2 n) (fib-it 1 0 n))

1.4.4 [习题]

函数f由如下规则定义: 如果n<3, 那么f(n)=n, 如果n>=3, 那么f(n)=f(n-1)+2f(n-1)+3f(n-3).分别实现递归和迭代版本.

;;递归
(define (f11 n)
  (cond ((< n 3) n)
  (else (+ (f11 (- n 1))
     (* 2 (f11 (- n 2)))
     (* 3 (f11 (- n 3)))))))
;; 迭代
(define (f11-it a b c n)
  (cond ((< n 3) a)
  (else (f11-it (+ a (* 2 b) (* 3 c)) a b (- n 1)))))
(define (f112 n) (f11-it 2 1 0 n))

写一个过程,采用递归计算出帕斯卡三角形

(define (psc n k)
  (cond ((> k n) 0)
      ((= n 0) 1)
  ((= k 0) 1)
  (else (+ (psc (- n 1) (- k 1))  (psc (- n 1) k)))))

1.13

排版渣表示这道题好不想敲啊…按照题目提示用数学归纳法证明等式比较容易,证明接近整数稍微需要一点想象力…

习题解如下, 各路学霸出没: http://sicp.readthedocs.org/en/latest/chp1/13.html

1.4.5 增长的阶

增长的阶 用以描述计算过程消耗计算资源的速率.

O(n): 规模增加一倍, 资源增加一倍
O(n²): 规模增加1, 资源增加常数倍. 比如树形递归占用空间是(ϕⁿ)
O(lg n):规模增加一倍, 资源增加一个常数.

1.4.6 [习题]

1.14 画出1.2.2节过程(count-change 11)的计算过程. 当现金量增加时,这一过程空间和步数增长的阶各是什么?
计算过程在纸上画了一遍…懒得搬上来了, 直接参考习题解里的图吧后面两个估算没有找到标准答案,先把自己的思路写在这里.

设现金量为n,币种数为m,则
- 步数增长的阶:
这个计算过程受到币种限制, 所以不能简单的用二叉树复杂度来估算. 根据计算过程cc, 当n比较小时(比如小于50), 复杂度为O(n). 当n比较大的时候, 复杂度正比于n能够被最大币种(这里是50)整除的次数. o(f(n))=(1+2+3+…n/50)*n = ((1+n/50)*(n/50)/2)*n = o(n²).
- 空间增长的阶: O(n+m).树的最大深度由n决定, 最深子树总是全部由1元钱凑成n的情况.
1.15 题目略.
[吐槽:原来可以这样实现sin,长姿势了]

如果解释器的代换模型是是 应用序 ,则这个问题是线性迭代:
- p将被使用多少次? 5次.
- 空间增长的阶: n/(3^k) = 0.1, k=log₃ (10*n), 所以是O(lg n)
- 步数增长的阶: O(lg n)
如果解释器是 正则序 ,则这个问题是树形迭代:
- p将被使用多少次? 1 + 4 + 4² + 4³ + 4⁴
- 增长的阶: O(4ⁿ)

1.4.7 求幂

快速求幂法fast-expt:

b^n = (b^(n/2))^2 ;;若n是偶数
b^n = b * b^(n-1) ;;若n是奇数

1.4.8 [习题]

1.16 用fast-expt的思路定义一个过程, 它按照迭代的方式产生出求幂的计算过程.

(define (expt-iter b n a)
  (cond ((= n 0) a)
  ((even? n) (expt-iter  (* b b)  (/ n 2)  a))
  (else (expt-iter  b (- n 1) (* b a)))))

1.17 用fast-expt的思路实现一个反复使用加法计算乘积的过程.

(define (fast-mul a n)
  (cond ((= n 0) 0)
  ((= n 1) a)
  ((even? n) (fast-mul (+ a a) (/ n 2)))
  (else (+ a (fast-mul a (- n 1))))))

1.18 求两个整数的乘积

(define (mul-iter b n a)
  (cond ((= n 0) a)
  ((even? n) (mul-iter (+ b b) (/ n 2) a))
  (else (mul-iter b (- n 1) (+ a b)))))

1.19 用对数步数计算菲波那切数列

这道题目是前面求幂过程的推广.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
  ((even? count)
   (fib-iter a
       b
       (+ (* p p) (* q q))
       (+ (* 2 p q) (* q q))
       (/ count 2)))
   (else (fib-iter (+ (* b q) (* a q) (* a p))
       (+ (* b p) (* a q))
       p
       q
       (- count 1)))))

1.4.9 最大公约数

GCD(a,b)=GCD(b,r), r是a除以b的余数.

(define (gcd a b)
  (cond ((= b 0) a)
  (else (gcd b (remainder a b)))))

1.4.10 [习题]

1.20 解释器是应用序和正则序时,上述算法求(206 40)的计算过程分别是怎样的,remander分别调用多少次

应用序

(gcd 206 40)
(gcd 40 6)
(gcd 6 4)
(gcd 4 2)
(gcd 2 0)
2

一共4次remander

正则序

(gcd 206 40)
cond ...
(gcd 40 (re 206 40)) ;;b=6
cond ...  ;; +1
(gcd (re 206 40) (re 40 (re 206 40))) ;;b=4
cond ...  ;; +2
(gcd (re 40 (re 206 40)) (re (re 206 40) (re 40 (re 206 40)))) ;;b=2
cond ...  ;; +4
(gcd .......) ;; b=0
cond ...  ;; + 7
a = (re (re 206 40) (re 40 (re 206 40) = (re 6 4) = 2 ;; +4

一共18次remander

1.4.11 素数检测

(终于学会打公式了○|￣|_)

本节描述两种检查整数n是否为素数的方法,第一个具有O($\sqrt{n}$)的增长阶, 第二个具有O(log n)的增长阶.

寻找因子:用从2开始的连续整数开始依次检查它们是否能整除n.如果n不是素数,必然有小于或等于 $\sqrt{n}$ 的因子,由此可知这个算法拥有O($\sqrt{n}$)的增长阶.
费马检查:O(log n)的检查基于数论中著名的费马小定理(数论全忘光了…桑不起)

费马小定理: 如果n是一个素数,a是小于n的任意正整数,那么a的n次方与a模n同余. 而如果= 不是素数 =,则大部分a<n都将满足上面的关系,这就引出了检查素数的算法: 如果发现不满足关系的a那么n肯定不是素数.

费马检查: 采用许多随机的a来检查,通过的检查越多则n是素数的概率越大.

首先定义一个O(log n)的迭代过程计算 $a^n$ 对m取模的结果(a<n,a<m)

(define (expmod bas exp m)
  (cond ((= exp 0 ) 1)
  ((even? exp)
   (remainder (square (expmod bas (/ exp 2) m)) m))
  (else
   ;;  $(a*a^{n/2}*a^{n/2})%n = (a%n)*(a^{n/2}%n)^2 = a*(a^{n/2}%n)^2
   (remainder (* bas (expmod bas (- exp 1) m)) m))))

其中关于连续求平方的推导如下:

$\gcd((a^{n/2}a^{n/2}),n)=\gcd(a^{n/2},n)\gcd(a^{n/2},n)=\gcd(a^{n/2},n)^2$

$\gcd((a*a^{n/2}a^{n/2}),n)=\gcd(a,n)\gcd(a^{n/2},n)^2=a*\gcd(a^{n/2},n)$

然后随机1和n-1之间的整数进行测试:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
  ((fermat-test n) (fast-prime? n (- times 1)))
  (else false)))

1.4.12 概率方法

费马检查的结果只有概率上的正确性..但能够证明存在使出错概率任意小的算法.

1.4.13 [习题]

使用smallest-divisor过程找出下面各数的最小因子:199,1999,19999

首先设计了一个(有点挫)的算法,从2到n遍历,寻找第一个能够整除n的素数.(能够想到的优化版算法只有素数表了orz.

(define (divisor-test a n)
  (cond ((= n 1) 1)
  ((= n 0) 0)
  ((and (fast-prime? a 10) (= (remainder n a) 0)) a)
  (else (divisor-test (+ a 1) n))))

(define (smallest-divisor n) (divisor-test 2 n))计算结果是199:199,1999:1999,19999:7.

观察查找素数的时间.题目略…
```
(define (search-for-prime n)
  (cond ((prime? n) 
  (display n))
  (else (cond ((even? n)
         (search-for-prime (+ n 1)))
        (else 
         (search-for-prime (+ n 2)))))))

(define (start-search-prime n start-time)
  (search-for-prime n)
  (newline)
  (display (- (real-time-clock) start-time)))

(define (time-for-search-prime n)
  (start-search-prime n (real-time-clock)))
```
一开始使用题目给的(runtime)计算时钟周期,结果无论后面加多少个零,结果几乎都在1e-2左右. 后来得知现在的MIT-scheme的runtime按秒计时,换成以tick计时的real-time-clock就对了.

测试结果是:
- 1000:1 (结果是1009,6次测试,平均0.17ms每次)
- 10000:1 (5,0.25)
- 100000:1 (3,0.33)
- 1000000:2 (3,0.67)
- 10000000:8 (10,0.8)
- 100000000:15 (5,3)
- 1000000000:37 (5,7.4)
- 10000000000:169 (10,16.9)
1000000以下的测试结果差别很小, 1000000以上差异是2.x倍, 可见测试结果与预期的$/sqrt{n}$不符.
修改本节开始的smallest-divisor过程,使其步数减半,并检验结果是否符合预期
```
(define (smallest-divisor-fast n)
  (let  ((t (real-time-clock)))
    (display (find-divisor-fast n 2))
    (- (real-time-clock) t)))

(define (find-divisor-fast n test)
  (cond ((> (square test) n) n)
  ((divides? n test) test)
  (else (find-divisor-fast n (next test)))))

(define (next n)
  (cond ((even? n) (+ n 1))
  (else (+ n 2))))
```
为了使差别比较显著,挑选2个相差10倍左右的素数进行测试:1009,10009
- (smallest-divisor-fast (* 1009 10009)) ==> 1
- (smallest-divisor (* 1009 10009)) ==> 2
- (smallest-divisor-fast (* 10009 10009)) ==> 9
- (smallest-divisor (* 10009 10009)) ==> 14
- (smallest-divisor-fast (* 20029 20029)) ==> 16
- (smallest-divisor-sqre (* 20029 20029)) ==> 26
可见fast版本速度比原有版本快,但两个算法速度比值比2小.

初步推测,当算法复杂度低且参数比较小时,这个算法本身的耗时在一个过程的执行过程中占比非常低. 而执行过程所需的大量递归调用,变量绑定等操作消耗掉绝大部分CPU资源,导致我们得到的结果不准确. 而当参数增大时,算法本身占用的资源比例变大,使得结果与我们的预测越来越接近.

所以估算算法复杂度并不能完全预测过程的实际执行时间.
使用fast-prime?代替prime?实现第二题.并检验结果是否符合预期.
把上上道题目代码中的prime?换成fast-prime就可以了.
```
(define (search-for-prime n)
  (cond ((fast-prime? n 50) 
  (display n))
  (else 
   (cond ((even? n)
    (search-for-prime (+ n 1)))
         (else 
    (search-for-prime (+ n 2)))))))
```
测试结果:
- 1000:2
- 10000:2
- 100000:3
- 10000000:4
- 1000000000000:8
差距比预期小的多,但参数越大差别越明显.解释见上一题.

[Mark] 学习完后面的内容可能会在解释器层面上对这个问题有新的见解,到时候再补充吧.
分析Alyssa的方法是否实用

Alyssa的方法理论上比本节的算法步数只有1步,但容易溢出. 本节的方法虽然步数多了一些, 但它不会真正进行巨大的乘幂运算, 所以本节的方法更加实用.
分析fast-prime?中的expmod使用显示乘法为何会把O(log n)的算法变成O(n)的.
下面把(expmod base (/ exp 2) m)简写为 ep(n)

使用乘法:
```
ep(n)
(* ep(n/2) ep(n/2))
(* (* ep(n/4) ep(n/4)) (* ep(n/4) ep(n/4)))
(* (* (* ep(n/8) ep(n/8)) (* ep(n/8) ep(n/8))) (* (* ep(n/8) ep(n/8)) (* ep(n/8) ep(n/8))))
...
```
展开后可得进行expmod运算的次数是 $2^{log_2{n}}=n$ 次

使用square:
```
ep(n)
(square ep(n/2))
(square (square ep(n/4)))
...
```
$log_2{n}$ 次

证明注脚47中列出的Carmichael数确实能骗过费马检查.

首先写一个过程,检验所有小于n的a,看 $a^{n}$ 是否与a模n同余.

(check-prime? 561) => #t
(check-prime? 1105) => #t
(check-prime? 1729) => #t
(check-prime? 2465) => #t
(check-prime? 2821) => #t
(check-prime? 6601) => #t

Miller-Rabin检查

把前面fast-prime过程中的fermat-test替换为miller-test

(define (miller-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= n 1) true)
  ((= times 0) true)
  ((miller-test n) (fast-prime? n (- times 1)))
  (else false)))

使用前面的carmichael数测试,结果都为#f

1.5 用高阶函数做抽象

在作用上,过程也是一类抽象,它们描述了一些对于数的复合操作,但不依赖特定的数,甚至不只用数作为参数.

高阶过程 是能操作过程的过程, 它能以过程作为参数,或者以过程作为返回值.

这也是lisp的一个厉害之处.

1.5.1 过程作为参数

教材🌰:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) next b))))

(define (cub n) (* n n n))
(define (add n) (+ n 1))
(define (sum-cube a b) (sum cub a add b))

使用其它高级语言实现这种过程作为参数的过程时,绝对不会这么简洁.

1.5.2 [练习]

上面的sum过程产生一个线性递归, 使用迭代方式重写该过程.

(define (sum term a next b)
  (define (iter n result)
    (if (> n b) 
  result
  (iter (next n) (+ result (term n)))))
  (iter a 0))

写一个product过程,返回在给定范围中各点的某个函数值得乘积.请说明如何用product定义faactorial.

;; 递归
(define (product a b term)
 (if (> a b)
       1
       (* (term a) (product (+ a 1) b term))))

;; 迭代
(define (product-iter a b next)
  (define (iter n result)
    (if (> n b) 
  result
  (iter (+ n 1) (* result (term n)))))
  (iter a 0))

;; 分子
(define (term-numer a)
  (cond ((odd? a) (+ a 1))
  (else (+ a 2))))
;; 分母
(define (term-deno a)
  (cond ((even? a) (+ a 1))
  (else (+ a 2))))

;; pi/4
(define (quarter-pi n)
  (/ (product 1 n term-numer) (product 1 n term-deno)))

请说明sum和product都是称为accumulate的更一般概念的特殊情况.使用accumulate定义出sum和product.

(define (accumulate combinder null-value term a next b)
  (if (> a b) null-value
      (combinder (term a) (accumulate combinder null-value term (next a) next b))))

(define (sum a b) (accumulate + 0 (lambda (a) a) 1 (lambda (a) (+ a 1)) 10))
(define (product a b) (accumulate * 1 (lambda (a) a) 1 (lambda (a) (+ a 1)) 10))

实现filtered-accumulate

(define (filtered-accumulate filter combinder null-value term a next b)
  (cond ((> a b) null-value)
  ((filter a) 
   (combinder (term a) 
        (filtered-accumulate filter combinder null-value term (next a) next b)))
  (else 
   (combinder null-value
   (filtered-accumulate filter combinder null-value term (next a) next b)))))

1.5.3 用lambda构造过程

为了省去单独定义一些简单函数的麻烦,引入lambda特殊形式来完成这类描述,而不必给每个过程绑定名字.

(lambda (x) (+ x 4))

实际上, (define (<name> <param …>) ()) 是lambda的一种语法糖.

(define (plus4 n) (+ n 4))

等价于:

(define plus4 (lambda (n) (+ n 4)))

lambda表达式可以用做 组合式的运算符:

((lambda (x) (+ x 4)) 1)

1.5.4 用let创建局部变量

lambda的另一个作用是创建局部变量,为此语言里有一个语法糖 let

(define (f x y)
 ((lambda (a b)
  (+ (* x (square a))
    (* y b)
    (* a b)))
  (+ 1 (x y))
  (- 1 y)))

用let形式可以简化为

(define (f x y)
 (let ((a (+ 1 (x y)))
       (b (- 1 y)))
   (+ (* x (square a))
      (* y b)
      (* a b))))

注意使用let约束的局部变量必须在let的body中.

let使人能在尽可能接近其使用的地方建立局部变量约束.
变量的值是在let之外计算的. 如下面过程

....
(let (x 3)
     (y x))

如果x在let之前的值是2,在let内x=3, 而y=2.

有时在过程内部define也有与let一样的效果:

(define (f x y)
  (define a (...))
  (define b (...))
  (+ a b))

1.5.5 [习题]

执行(f f)会发生什么

(f f)->(f 2)->(2 2). 而2不是一个可以应用的过程, 会报错.

1.5.6 过程作为一般性的方法

通过区间折半法寻找方程的根

代码略…

找出函数的不动点

数x称为函数f的不动点,如果x满足方程 $f(x)=x$ .

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
    next
    (try next)))) ;; 这里需要保证收敛
  (try first-guess))

1.5.7 [习题]

使用fixed-point找出黄金分割 $phi$ 的值: x->1+1/x.
```
(fixed-point (lambda (x) (+ 1 (/ 1 x)))  1.0)
```
x=1.6180327868852458
修改fixed-point,使他打印出计算过程.确定x^x=1000的一个根,并比较采用平均阻尼和不用平均阻尼的计算步骤.
不用平均阻尼
```
(fixed-point-log  (lambda (x)  (/ (log 1000) (log x))) 2)
```
33步

使用平均阻尼:
```
(define (average n) (/ n 2))
(fixed-point-log  (lambda (x) (average (+ x (/ (log 1000) (log x))))) 2)
```
8步

一个无穷连分式是一个如下形式的表达式:

$\Large x=\frac{N_1}{D1 + \frac{N_2}{D2 + \frac{N_3}{D_3+...}}}$ 证明当Di和Ni都等于1时,这一连分式产生出$1/\phi$

;; 递归
(define (cont-frac n d k it)
  (cond ((= it k) 0)
  (else (/ (n it) (+ (d it) (cont-frac n d k (+ it 1)))))))

(define (gold k)
    (+ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k 0)))

(gold 11)

;; 迭代
(define (cont-frac-it n d k result)
  (cond ((= k -1) result)
  (else (cont-frac-it n d (- k 1) (/ (n k) (+ (d k) result))))))

(define (gold k)
    (+ 1 (cont-frac-it (lambda (i) 1.0) (lambda (i) 1.0) k 0)))

(gold 11)

k取6时结果具有4位精度, 但不够准确.k越大时,结果越逼近 $1/\phi$, k取12时,小数点后4位的结果是准确的.

使用上一题的cont-frac过程基于欧拉展开式求e的近似值.

(define (ora i)
    (cond ((= 0 (remainder (- i 1) 3))
     (* 2 (/ (+ i 2) 3)))
    (else 1.0)))

(define (de-frac k)
  (cont-frac-it
  (lambda (i) 1.0)
  ora
  k
  0))

(define (e k)
  (+ 2 (de-frac k)))

定义过程(tan-cf x k),基于Lambert公式计算正切函数的近似值.

(define (tan-cf x k)
  (define (N-tan i) 
    (if (= i 1)
  x
  (- (square x))))
  (define (D-tan i) (- (* 2 i) 1))
  (cont-frac N-tan D-tan k 1))

(tan-cf 1.0 10)
(tan 1)

1.5.8 过程作为返回值

把前面所说的平均阻尼概念再抽象一下..

(define (average-damp f)
  (lambda (x) (average x (f x))))

((average-damp square) 10)

这样前面求平方根的过程可改写成:

(define (squrt x)
  (fixed-point (average-damp (lambda (a) (/ x a))) 1.0))

所以现在上面这两行代码中结合了三种思想: 不动点搜寻,平均阻尼,和函数y->x/y.

牛顿法

首先需要有一个方法描述导数

$Dg(x)=\frac{g(x+dx)-g(x)}{dx}$ 这时就能看到将过程作为返回值的威力了:生成导数函数.

(define dx 0.00001) ;; 首先定义一个delta
(define (drive g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
;; test: $D(x^3)=3*x^2$
((drive (lambda (x) (* x x x))) 2)

然后把牛顿法描述为一个求不动点的过程:

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((driv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g ) guess))
(define (squr x)
  (newtons-method (lambda (y) (- (square y) x)) 1.0))

抽象和第一级过程
计算机程序总会对计算元素的可能使用方式加上某些限制.带有最少限制的元素被称为 第一级状态 第一级元素的某些"特权"包括:
- 可以使用变量名
- 可以提供给过程作为参数
- 可以由过程作为结果返回
- 可以包含在数据结构中
List给了过程完全第一级状态, 这是非常牛逼的(主要是难以实现). 我日常用的几种语言没有谁能做到这些orz

1.5.9 [习题]

请定义一个过程cubic,它和newtons-method一起使用在下面的表达式里,逼近三次方程x³+aX²+c的零点
(newtons-method (cubic a b c) 1)
```
(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))
;; test
(newtons-method (cubic 3 1 1) 1)
```
请定义一个过程double,它以一个有一个参数的过程作为参数,double返回一个参数.这一过程将原来那个参数过程应用两次.
```
(define (double f)
  (lambda (x) (f (f x))))
;; test
((double (lambda (x) (square x))) 2)
```
表达式(((double (double double)) inc ) 5)返回21:
```
(((double (double double) inc) -> (double (double (double (double inc)))) = 2^4 = 16
```

定义compose实现复合函数

(define (compose f g)
  (lambda (x) (f (g x))))
((compose square inc) 6)

构造f的n次重复应用过程

(define (repeated f k)
  (define (it g k n)
    (if (= n (- k 1)) 
  (lambda (x) (g x))
  (it (lambda (x) (f (g x))) k (+ n 1))))
  (it f k 0))

((repeated square 2) 5)
; Value: 625

实现平滑函数

(define (smooth f)
  (lambda (x) 
    (/ (+ (f x) (f (- x dx)) (f (+ x dx))) 3)))

(define (smooth-k f k)
  ((repeated smooth k) f))

试验求$x/y^n-1$需要多少次平均阻尼

;;前面定义的求幂过程expt-iter
(define (expt-iter b n a)
  (cond ((= n 0) a)
  ((even? n) (expt-iter  (* b b)  (/ n 2)  a))
  (else (expt-iter  b (- n 1) (* b a)))))
;;定义过程x->x/y^n
(define (root n x)
  (lambda (y) (/ x (expt-iter y n 1))))
;;应用k次阻尼
(define (repeated-damp f k)
  ((repeated average-damp k) f))

(define (squrt-n n x damp-cnt)
  (fixed-point-log (repeated-damp (root n x) damp-cnt) 1))

试验下来大约至少需要$log{n}$次平均阻尼.

写一个过程interative-improve, 它以两个过程为参数. 其中之一用于判定结果是否足够好,另外一个用于猜测更好的结果.

(define (iterative-improve good-enough? f)
  (lambda (x)
    (define (try guess)
      (let ((next (f guess)))
  (if (good-enough? guess next)
      next
      (try next))))
    (try x)))
;;定义good-enough?
(define (close-enough? v1 v2)
  (< (abs (- v1 v2)) tolerance))

(define (fixed-point f guess)
  ((iterative-improve close-enough? f) guess))

(define (sqrt n guess)
    ((iterative-improve 
      close-enough? (lambda (x) (/ (+ x (/ n x)) 2))) guess))

以上.

(几乎一个月过去了/(ㄒoㄒ)/~~)