1. 构造过程抽象¶

1.1. 程序设计的基本元素¶

程序设计语言不仅是一种指挥计算机执行任务的方式，还应该成为一种框架，使我们在其中组织自己有关计算过程的思想。程序语言提供了：基本表达形式、组合的方法、抽象的方法。

基本表达形式，用于表示语言所关心的最简单个体
通过组合的方法可以从较简单的东西出发构造出复合的元素
通过抽像的方法可以为复合对象命名，并将它们当作单元去操作

1.1.1. 表达式¶

用Racket交互式窗口可以执行单条语句。Racket是前缀表达的，所以要表达137与349的和要写成

(+ 137 349)

这种表达式称为组合式，由一对括号括起的表达式，形成一个表，用于表示一个过程应用。最左的元素为运算符，其它元素都是运算对象。从数学上加法是两个元素之间的运算，但是用这种组合式可以直接表示任意个参数的运算，例如下列语句也是合法的：

(+ 21 35 12 7)

这种组合式的另一优点是可以直接扩充，允许组合式的嵌套。

(+ (* 3 5) (- 10 6))

1.1.2. 命名和环境¶

程序语言一个必不可少的方面就是提供一种用名字去使用计算对象的方式，Racket当中使用define命名

(define size 2)
(* size 5)
(* 5 size)

(define pi 3.1419)

define是最简单的抽象方法，允许我们用一个简单的名字引用一个组合运算的结果。计算得到的对象完全可以具有非常复杂的结构，如果每次使用都必须重复记住使用细节那是极端不方便的事，实际上构造一个复杂程序也就是一步步创建出越来越复杂的计算性对象，解释器使这种逐步的构造过程变得非常方便。复杂程序绝大多数也是由一个个简单计算对象组成的。

1.1.3. 组合式的求值¶

要求值一个组合式，就进行：

求这个组合式的所有子表达式

作为组合式的最左表达式（运算符)的值的过程应用于相应的实际参数。

这可以叫作“一般性求值规则”。对于一般性求值规则中，所有的运算内容都是组合和基本表达式，例如数字、内部运算符或其它名字这些基础情况，基础情况归纳起来就是：

数的值就是它所表示的本身的数值

内部运算符的值就是能完成相应操作的机器指令序列

其它名字的值就是环境中关联于这个名字的对象

在求值规则中没有处理define，因为(define x 3)并不是将define应用于一个实际参数，而只是进行了一个关联操作。

define是”一般性求值规则”中不进行处理的”特殊形式”，每个特殊形式都有其自身的求值规则。各种不同的表达式（每种有与之相关联的求值规则）组成了程序语言的语法形式。

1.1.4. 复合过程¶

接下来定义过程，这是一种威力能强大的抽象技术。通过它可以为复合操作提供名字，之后就可以为这种操作作为一个单元使用。

(define (square x) (* x x))
(define (add3 x) (+ 3 x))

这种定义的一般形式是

(define (<name> <formal parameters>) <body>)

其中，<name>是一个符号，过程定义将在环境中关联这个符号。定义这个符号后就可以使用它

(square 2)
(add3 7)
(+ (square 3) (square 4))

1.1.5. 过程应用的代换模型¶

对于复合过程

(define (sum-of-square a b) (+ (square a) (square b) ) )

(define (f x) (sum-of-square (+ a 1) (* a 2) ))

要求 (f 5)的值，首先提取出f的体

(sum-of-square (+ a 1) (* a 2))

然后将实际参数5替换其中形式参数

(sum-of-square (+ 5 1) (* 5 2))

这样形成

(sum-of-square 6 10)

再将sum-of-square应用于6和10归约为:

(+ (square 6) (square 10))

利用square的定义再归约为

(+ (* 6 6) (* 10 10))

进一步求值即

(+ 36 100)

最后即得最终的运算结果为136。

在之前所说的”一般性求值规则”当中，解释器会先对运算对象求值而后将得到的过程应用于实际参数。然而这并不是执行求值的唯一可能。另一种求值模型，是先不求运算对象的值，直到需要它们的值的时候再求，用这种求值方式就应该先用运算对象表达式对代换形式参数，直到得到一个只包含基本运算符的表达式，然后再执行。例如求(f 5)则按如下序列：

(sum-of-square (+ 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

像这种“完全展开而后归约的”求值模式称为“正则序求值”，与之对应的是当前解释器使用的“求值参数后应用”的方式，称为“应用序求值”，可以证明，对那些可以通过替换去模拟，并产出合法值的过程应用，采取正则序和应用序是得到相同的值，具体两种求值模型的内在性质将在后边讨论。

1.1.6. 条件表达式和谓词¶

目前定义的过程还非常有限，因为还没办法做某些检测并依据检测的结果去确定做不同的操作。例如，根据一个数字的正负性分别返回1,0或-1,这需要进行分情况分析，对这类分情况分析的形式，使用形式为

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...

      (<pn> <en>))

这里首先包含一个符号cond，在它之后用一些称为“子句”的表达式对偶，在每个对偶中第1个表达式是谓词，也就是它是一个表达式，它的值将被解释成真或假。

cond的求值方式是先求谓词p1的值，若它为false则求谓词p2，若再为false就继续求p3，直到发现某个谓词为真的时候，这时cond的值就是这个谓词p所对应的序列表达式e的值，如果没有找到值为真的p，cond的值就没有定义。

在cond中有个特殊的符号，就是在所有谓词都不成立时，则会用else之后指定的序列表达式的值。

if是条件式的受限形式，适用于只有两情况，一般形式为

(if <predicate> <consequent> <alternative>)

在求一个if表达式时，先从<predicate>开始，若<predicate>得到真，解释器就从<consequent>取得表达式的值，否则就取<alternative>的值。

注解

if和cond有一点小区别，在于cond子句的<e>可以是表达式序列，对应的<p>为真的时候<e>中的表达式就会顺序地求值并将其中最后一个表达式的值作为cond的值返回。而if中<consequent>和<alternative>都只能是单个表达式。

除了基本谓词<,=,>之外，还有逻辑复合词如and,or,not

(and <e1> <e2> .. <en>)
(or <e1> <e2> .. <en>)
(not <e>)

1.1.7. 实例：用牛顿法求算术平方根¶

接下来用一个比较常用的数学函数作为示例，即平方根函数。这里用牛顿法求平方根，牛顿法是求函数零点的通法.要求

\[f(x)=0\]

的解，即求

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

的收敛点，通过多次迭代就可以计算出在指定精度下的函数零点。

对于求k的算术平方根，也就是x*x-k=0的大于0的解，即函数f(x)=x*x-k大于0的零点。

先用自然语言描述这个求解的过程：:

尝试当前估计值是否符合条件，若已经符合：
估计值就是结果
否则
改进估计值并尝试

用我们Racket写出来就是

(define (sqrt-iter guess k)
    (if (good-enough? guess k)
        guess
        (sqrt-iter (improve guess k) k)
    )
)

其中sqrt-iter就是我们的尝试的入口，guess是估计值，如果猜测值可以满足精度要求就以这个估计值作为表达式的值。否则就换一个估计值（当然要向更“好”的方向换）并重新试，直到试到足够好。

sqrt-iter已经完成了，但其中的good-enough?和improve还没有设计。对于计算算术平方根的问题，通过牛顿法的数学运算:

\[ \begin{align}\begin{aligned}x_{n+1} &= x_n - \frac{x_n^2-k}{2x_n}\\ &= x_n - \frac{1}{2}(x_n-\frac{k}{x_n})\\ &= \frac{1}{2}(x_n+\frac{k}{x_n})\end{aligned}\end{align} \]

guess就是迭代值xn,k就是被开方数。这样improve可写成：

(define (improve guess k)
    (define (average x y)
        (/ (+ x y) 2 ) )
    (average guess (/ k guess))
)

另一部分good-enough?只需要判断我们的猜测与实际值相差是否小于允许的误差，这个”?”只不过是命名风格上的约定，用来表示这是一个谓词，对于解释器来说，这不过是一个普通的字符。

(define (good-enough? guess x)
    (define epsilon 0.00001)
    (define (square x) (* x x) )
    (< (abs (- (square guess) x ) ) epsilon )
)

最后，我们还需要一个guess来启动工作。在这个运算中我们总可以用1.0作为初始估计值作为起始值。

(define (sqrt x) (sqrt-iter 1.0 x))

将这些定义都送入解释器，执行(sqrt x)就可以计算x的算术平方根了。

1.1.8. 过程作为黑箱抽象¶

sqrt是我们自定义计算过程的一个例子，这儿sqrt-iter的定义是递归的，也就是说，这一过程的定义基于它自身。除了递归之外，先讨论在这个过程中显示的其它要点。

计算算术平方根的过程中可以自然地被分解为若干问题：估计值是否足够好，如何改进一个估计值。而这些问题又会衍生一些问题：改进时需要计算平均值等等。

当我们在看good-enough?中的square时，square就类似一个黑箱，我们并不需要关心square当中是如何实现的，只要它能计算出数值的平方就可以。可以说这就是一个过程抽象，在这个层次上，任何能计算平方的过程都可以用作square，例如下列两个过程都可以得到x的平方：

(define (square1 x) (* x x))

(define (square2 x)
    (define (double x) (+ x x))
    (exp (double (log x)))
)

由此可知，一个过程定义应该能隐藏一些细节，使过程的使用者可能不必自己去写这些过程，而是直接使用一个黑箱并且接受它。

隐藏的细节之一就是局部名，也就是形式参数，形式参数具体是什么根本不重要，例如之前good-enough?所用的两个参数名为guess和x，只要在这个过程中能完成good-enough?的功能，采取什么形式参数都不会影响结果。

另外就是内部定义，这类似于其它程序语言的作用域，例如improve中的average的定义，在improve之外就不会有average生效，或者其它地方用average可以有其它的实现不受improve内的average影响。

将前述sqrt-iter等操作都置于(sqrt x)当中，这中间的所有内容都是内部函数的操作，可以免去在各个函数中传x参数。

(define (sqrt x)
    (define (good-enough? guess)
        (define (square x) (* x x))
        (define epsilon 0.000001)
        (< (abs (- (square guess) x ) ) epsilon ) )
    (define (improve guess)
        (define (average x y) (/ (+ x y) 2) )
        (average guess (/ x guess) ) )
    (define (sqrt-iter guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess))
        )
    )
    (sqrt-iter 1.0)
)

1.2. 过程与它们产生的计算¶

一个过程也就是一种模式，它描述了一个过程的局部演化方式。例如，我们利用阶乘定义n!=n * (n-1) * (n-2) * … * 2 * 1，对于计算正整数n的阶乘，就是n乘以n-1的阶乘，直到算出1的阶乘为1.

(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1) ) )
    )
)

这样定义的计算叫作“递归计算过程”，要执行这种计算过程，解释器需要维护好那些以后要执行的操作的轨迹，这个计算是一个乘法，轨迹中的信息量是正比于计算量的，这样的计算过程称为“线性递归过程”。

还可以用另一种观点计算阶乘：

product <- conter * product
counter <- counter + 1

n!就是计数器counter超过n时的product的值。

(define (factorial n)
    (define (fact-iter product counter max-count)
        (if (> conter max-conter)
            product
            (fact-iter  (* counter product)
                        (+ counter 1)
                        max-count
            )
        )
    )
    (fact-iter 1 1 n)
)

这样的计算过程没有增长或收缩，对于计算中的每一步都保存在参数当中，称这种计算过程为“迭代计算过程”。一般说迭代过程就是其状态可以用固定数目的状态变量描述的计算过程。递归计算过程中有许多信息并没有明示，而是由解释器进行维护。

不要混淆递归计算过程与递归过程。若谈到某个过程是递归的，就是说在语法形式上它是在定义中（直接或间接地）引用了自身。而递归计算过程是与迭代计算过程相对的一种计算过程的进展方式，而不是相应过程书上的语法形式。

1.2.1. 树形递归¶

树形递归是非常常见的计算模式，例如Fibonacci数列：

\[\begin{split}Fib(n) = \begin{cases} &0 ,n=0 \\ &1 ,n=1 \\ &Fib(n-1) + Fib(n-2),otherwise \end{cases}\end{split}\]

很容易定义这样一个递归过程:

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

不过这种计算方式比较糟糕，因为在它执行了太多冗余计算。可以证明这样的过程计算步骤是随输入而指数增长的。另外空间上会随着输入而线性增长。

我们可以规划另一种计Fib(n)的方法

a <- a+b
b <- a

不难证明，在应用n次变换之后，a和b将分别等于Fib(n+1)和Fib(n)。这两种计算方式所需的步骤差异巨大。

但是我们也不能下结论说树形递归计算就没有用处，如果考虑的是在层次结构性的数据上操作，而不是对数操作时，将会发现树形递归是一种自然的威力强大的工具。即使是对数的计算，树形递归计算过程也可能帮助我们理解和设计程序

1.2.2. 实例：素数检测¶

1.2.2.1. 寻找因子¶

(define (smallest-divisor n)
    (find-divisor n 2))
(define (find-divisor n test-divisor)
    (cond   ((> (square test-divisor) n) n)
            ((divides? test-divisor n) test-divisor)
            (else (find-divisor n (+ test-divisor 1)))
    )
)

(define (divides? a b)
    (= (remainder b a) 0) )

(define (prime? n)
    (= n (smallest-divisor n)))

n的最小因子就是n的话，那么n就是素数。

find-divisor的结果依据的是：如果n不是素数，那么它必定存在一个小于等于 \(\sqrt{n}\) 的因子，此方法就是只需要在此范围内检查因子即可，确定素数所需要的步数将具有 \(\Theta (\sqrt{n})\) 的增长阶

1.2.2.2. 费马检查¶

利用费马小定理，可以在 \(\Theta (\log{n})\) 的时间内检查素数。

注解

费马小定理：如果n是一个素数，a是小于n的任意正整数，那么a的n次幂与a是模n同余的。

（如果两数模n的余数相同，则称它们是模n同余的）

如果n不是素数，那么一般而言，大部分的 \(a<n\) 都满足这个关系。这就引出下述检查素数的算法：给定整数n，任意取一个a<n并计算 \(a^{n}\) 取模n的余数。如果得到不等于a，那么n就肯定不是素数。如果它是a，那么a是素数的机会就很大。这时再另外随机取一个a并采取相同的方法检查。如果它满足上述等式，那么我们就能对n是素数有更大把握，通过检查越来越多的a值，就可以不断增加我们认为n是素数的信心。

(define (expmod base exp m)
(cond   ((= exp 0) 1)
        ((even? exp)
            (remainder (square
                (expmod base (/ exp 2) m )) m) )
        (else (remainder (* base (expmod base (- exp 1) m ) ) m )
        )
)
)

执行费马检测需要选取位于[1,n-1]上的数a，而后检查a的n次幂取模n的余数是否等于a。我们另外指定一个尝试次数，将进行这么多次的检查，如果每次检查都成功，则这一过程的值就是真。否则为假

(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   ((= time 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)
)
)

1.2.2.3. 概率方法¶

从特征上看，费马检查与之前的算法不一样，费马检查得到的结果只有概率上的正确性：如果n不能通过费马检查，则它不定不是素数，而n通过了费马检查只能作为它是素数的一个证据但并不能作为保证。可以说如果执行检查的次数足够多，并且所有的n都通过了检查，就可以将这一素数检测出错的概率减到任意可接受的程度。

不过这一断言并不完全正确，因为确实存在一些数字能骗过费马检查，不过这些数字极其罕见，因此费马检查还是比较可靠的。

注解

能够骗过费马检查的数称为Carmichael数，在100,000,000之内有255个，其中最小的几个是561,1105,1729,2465,2821,6601.

在对大数进行素性检测时，碰到这种能骗过费马检查的值的几率是极小的，甚至说比宇宙射线导致计算机执行正确算法时崩溃的几率还要小。所以在大数上可以进行利用费马定理素性检测也体现了工程上也数学研究上的不同。

1.3. 用高阶函数做抽象¶

在作用上，过程也就是一类抽象，它们描述了一些对于数的复合操作，但又不依赖特定的数。而在计算过程中，如果将过程限制为只能以数为参数那会严重地影限制我们建立抽象的能力，所以我们需要构造过程，使之以过程为参数，或者以过程为返回值，这类能操作过程的过程称为“高阶过程”。将过程作为参数极大地增强了语言的表述能力。

考虑下列三个过程：

计算a到b的各整数之和

计算a到b之间各数的立方之和

计算 \(\frac{1}{1\times3}+\frac{1}{3\times5}+\frac{1}{5\times7}+...\)

这三种过程都共享一种公共的基础模式,那就是从a开始累加到b为止，不同点在于所加的项不同，提供下一个a值的过程也不同。我们可以抽象这样一个模板

(define (<name> a b)
(if (> a b)
    0
    (+ (<term> a)
        (<name> (<next> a) b)
    )
)

这样的公共模式说明实际上确实存在一种很强的抽象。就像数学上早就认识到序列求和中的抽象模式，并提出专门的求和记法：

\[\sum_{n=a}^{b}{f(n)}=f(a)+...+f(b)\]

用于描述这一概念。求和记法的威力已经在于它使数学家能处理求和的概念本身，而不是只是某种特定的求和。

作为程序模式，我们也希望使用的程序足够强大，可以写出一个过程去表述求和的概念，而不是只是对于特定求和写出过程。实际上，在上述抽象出来的模板中使用形式参数代替空位就可以

(define (sum term a next b)

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

例如，要计算从a到b各数的立方之和，就可以用：

(define (inc n) (+ n 1))
(define (sum-cubes a b)
    (sum cube a inc b)
)

1.3.1. 用lambda构造过程¶

而像(inc n)这样非常简单的过程有时并不需要定义，有lambda运算就不需要为这样简单过程再起个名字，它只需要刻画“返回值为输入值+1”的过程就可以。

注解

这一形式取自lambda演算，由数理逻辑学家Alonzo Church引入的一种数学计法，为研究函数应用提供了一个严格的基础，lambda演算已经成为程序设计语言语义的数学基石。

lambda的定义为：

(lambda (<formal-parameters>) <body>)

这与define的结构是完全一样的，区别在于lambda不需要为这个过程命名，直接说明了这个过程的功能。利用lambda，重新写出计算立方数之和：

(define (sum-cubes a b)
    (sum cube a (lambda (x) (+ x 1)) b)
)

lambda另一应用是创建局部变量。在一个过程中，除了一些已经约束为过程参数的变量之外，常常需要一些局部变量，例如：

\[f(x,y)=x(1+xy)^2+y(1-y)+(1+xy)(1-y)\]

可能更希望它被表述为：

\[\begin{split}a &= 1+xy \\ b &= 1-y \\ f(x,y) &= xa^2+yb+ab\end{split}\]

实现这样的过程就是利用辅助过程去约束局部变量

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

当然，也可以用一个lambda表达式，用来描述局部变量。

(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 ( (<var1> <exp1>)
        (<var2> <exp2>)
        (<var3> <exp3>)
        ...
        (<varN> <expN>))
    <body>
)

由于let在接近它使用的地方建立起局部的约束。并且要注意，变量的值是在let之外计算的，如果局部变量与某些变量同名时，其值仍按变量而非局部变量。例如

(let ((x 3)
      (y (+ x 2)))
    (* x y)
)

在计算y时所取的x的值是外部的值，而不是局部的值为3的x。

1.3.2. 过程作为一般性的方法¶

区间折半查找方程的根

(define (search f neg-point pos-point)
    (let ((midpoint (average neg-point pos-point)))
     (if (close-enough? neg-point pos-point)
      mid-point
      (let ((test-value (f midpoint)))
        (cond ((positive? test-value)
                (search f neg-point midpoint))
                ((negative? testvalue)
                (search f midpoint pos-point)
                )
                (else midpoint)
      )
     )
    )
)

寻找函数不动点