1.3 Formulating Abstractions with Higher Order Procedures - CloneableX/SICP-learning GitHub Wiki
在之前的章节我们已经见识过程式，它是一种对操作符及数字结合的抽象，并且它不拘泥于某个特定数字。如下：
(define (cube x) (* x x x))
关于上述程式，我们并不会将它作为某个数的立方谈论，而是将它视为获取任意数字的立方运算结果看待。当然要达成相同的目的也可以直接通过表达式，例如：
(* 3 3 3)
(* x x x)
(* y y y)此时无需提及 cube 运算。虽然直接使用表达式也能实现目标，但会带来一些缺陷，这将导致我们只能在基础操作符这一层面处理表达式，而无法使用更级别的运算。虽然通过表达式可以使程序计算立方结果，却使这门编程语言失去了表述立方概念的能力。在之前的内容中我们提到过，一门强大的编程语言应该拥有通过命名将模式抽象，并在其它地方直接使用它的能力，而程式提供了这样的能力。这也是绝大多数基础编程语言都提供定义程式能力的原因。
如果程式的参数只能为数字，这将极大地限制我们抽象的能力。因为我们将会在很多场景下遇到将相同的编程模式作为程式参数的情况，如果要恰当地表述这些模式的概念则需要通过定义程式实现，也就是说我们需要程式能够作为参数和返回结果的方式出现。这种维护程式的程式被称为 高级程式（higher-order procedures）。本节内容将向你展示高级程式这种强大的抽象能力，以及它为编程语言提供的强大表达能力。
思考下列三个程式，第一个程式计算了从 a 到 b 之间整数的和：
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))第二个程式计算 a 到 b 之间整数的立方之和：
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a)
(sum-cubes (+ a 1) b))))第三个程式计算下列数列的和：
结果趋近于 ，程式如下：
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2)))
(pi-sum (+ a 4) b))))其实这三个程式都包含了同样的模式。除去程式名称不一样外，它们都通过一个函数计算当前需要加上的值，然后再通过另一个函数计算下一次要用上的数字 a。上面的程式都可以通过在下列模板的替换位填写相应的程式生成，模板如下：
(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b))))这个通用模式更加验证了此处有一个抽象正待提取。事实上，这个抽象在数学上被称为数列求和，通过 sigma 表达式呈现，如下：
上述数学表达式强大之处在于它统一表达了求和的概念，而不是只描述某一个求和过程。相应的，程度设计师们也赋予了 Scheme 同样的类似的能力，我们能够编写程式表述求和概念本身，而不只是计算某种特定的求和。通过提供之前展示的模板及需要填入的对应程式即可，如下：
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))上述程式只需要数列的两个极限值以及 term 和 next 程式，接着便可以将其用于之前的求和程式中。例如，通过 sum 程式重新定义 sum-cubes：
(define (inc n) (+ n 1))
(define (sum-cubes a b)
(sum cube a inc b))也可以按类似的方式重写 sum-integers，比如：
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b))同样，重写 pi-sum 也不在话下，如下列程式：
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))一旦我们拥有了 sum 程式，我们便可以用它构建其他相关的概念。比如，定义由 a 到 b 的积分函数，公式如下：
其中 dx 为一个较小数值，我们可以将上述数学表达式表述了一个程式：
(define (integral f a b dx)
(define (add-dx x)
(+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
(integral cube 0 1 0.01)
.24998750000000042
(integral cube 0 1 0.001)
.2499998750000010 到 1 的立方积分准确结果为 1/4。
在上一节内容中使用的 sum 程式，它的使用有一些别扭，因为我们需要定义并将 pi-term 和 pi-next 程式作为参数传入高级程式中。与定义 pi-term 和 pi-next 相比，如果能够直接指定需要运算的过程将更加方便，下面介绍的 lambda 可以帮助我们达成此目的。通过 lambda 我们可以直接描述自己的需求，例如：
(lambda (x) (+ x 4))
(lambda (x) (/ 1.0 (* x (+ x 2))))然后 pi-sum 程式便可以在不定义 pi-term 和 pi-next 的基础上表述为如下程式：
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))通过 lambda 我们也可以在不定义其它程式的基础上重写 integral 程式，如下：
(define (integral f a b dx)
(* (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx))lambda 在定义程式上除了没有对程式命名外，与 define 的功能没有区别，它的结构体如下：
(lambda (<formal-parameters>) <body>)
事实上 (define (plus4 x) (+ x 4)) 与 (define plus4 (lambda (x) (+ x 4))) 是同等的。
就像表达式可以将程式作为操作符一样，lambda 表达式也可以作为表达式的操作符使用，例如：
((lambda (x y z) (+ x y (square z)))
1 2 3)
12这种使用方式就如同在定义了某个程式的环境中，可以通过程式名字直接使用程式一样。
lambda 的另一种用途就是创建局部变量。在程式中，我们不仅会用到传入的形参，也会用到局部变量。比如，假设我们打算计算如下函数：
也可以表述为：
在编写一个程式计算 f 函数时，需要的可能不止 x 和 y，同时还有中间变量 a 和 b。有一种方式是通过辅助程式绑定局部变量：
(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，通过 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>)
...
(<varn> <expn>))
<body>)let 表达式的第一部分是一组组名字与表达式，当 let 进行运算时，每个变量名都将关联对应表达式的结果，而 let 体中是使用这些局部变量运算的表达式。等同于 lambda 的如下形式：
((lambda (<var1> ... <varn>)
<body>)
<exp1>
...
<expn>)其实并没有设立新的机制让解释器提供局部变量，let 表达式只是一个 lambda 表达式的语法糖。从 let 的结构能够了解到，其中定义的局部变量作用域仅在对应的 let 表达式体中。根据此原理我们可以解析以下情况。
-
let仅允许被绑定的变量在此let表达式体中应用。例如，假设下列表达式中的 x 值为 5，整个表达式的结果为 38。因为在let体中应用的 x 值为 3，所以let表达式的结果为 33，而let表达式外部的 x 依然是 5，所以整个表达式的结果为 38。
(+ (let ((x 3))
(+ x (* x 10)))
x)-
let中局部变量值的计算依靠let外部的变量。也就是说，let中存在与表达式外部同名的变量，在计算let中局部变量结果时使用的依然是外部变量。例如，假设下列表达式中 x 的值是 2，整个表达式的结果为 12。因为let表达式中 x 值为 3，y 的值为 4（计算 y 时使用的 x 值为let外部的 x 值 2）。
(let ((x 3)
(y (+ x 2)))
(* x y))有时我们也可以通过内部定义程式的方式达到 let 的效果。比如，我们可以将之前的 f 程式修改为：
(define (f x y)
(define a (+ 1 (* x y)))
(define b (- y))
(+ (* x (square a))
(* y b)
(* a b)))但是我们更偏好使用 let 定义局部变量，定义内部程式时才使用 define。
在以前的章节我们介绍了复合程式是一种多个运算操作的组合抽象。在上一节的 integral 程式中我们也见识了更加强大的抽象方式，就是将程式作为计算的通用方法处理。在本节我们将更详尽地讨论两个示例（查找零点和固定点的函数），了解程式是直接作为通用方法使用的机制。
半区间法是一种简单实用的求方程根的方法，比如 f(x)=0（其中 f 是连续函数）。使用半区间法时，首先假设存在 a 和 b 满足 f(a) < 0 < f(b)，那么 f 函数零点肯定处于 a 至 b 之间。要找到零点，只需要给定 a 与 b 的平均数 x，并计算 f(x) 的结果。如果 f(x) < 0 则 f 函数的零点介于 x 与 b 之间。继续上述步骤，我们便可以不断缩小零点所在的区间，当找到零点时结束整个流程。在零点确定前，需要进行 步区域缩减操作，其中 L 表示初始区域的长度，T 表示确认零点时区域的长度。将上述步骤改写为程式如下：
(define (search f neg-point pos-point)
(let ((midpoint (average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond ((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint))))))我们假设初始时提供了函数 f 及满足条件的正数点和负数点。程式首先会计算两个点的中点，然后再检查目前的区域是否足够小，如果足够小将中点作为结果直接返回。否则将计算中点应用函数 f 后结果，如果结果为正数搜查零点的区间缩小为负数点至中点间；如果结果为负数，搜查零点的区间缩小为中点至正数点间；如果结果为零，中点就是我们要找的零点。
检查区域是否足够小可以参考之前的 good-enough? 程式，所以 close-enough? 如下：
(define (close-enough? x y) (< (abs (- x y)) 0.001))
如果直接使用 search 时传入的正负数点不对将引起结果的错误。所以我们要通过 half-interval-method 程式使用 search，由它负责保障正负数点参数的正常。程式如下：
(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond ((and (negative? a-value) (positive? b-value))
(search f a b))
((and (negative? b-value) (positive? a-value))
(search f b a))
(else
(error "Values are not of opposite sign" a b)))))下面是一些半区间法的实例：
(half-interval-method sin 2.0 4.0)
3.14111328125
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
1.0
2.0)
1.89306640625
给定一个数 x，对于函数 f 存在 f(x)=x 关系，则称 x 为函数 f 的固定点。对于一些函数，我们可以通过猜想，然后不断代入函数 f，直到结果不再发生剧烈的变化即可。数学公式如下：
f(x), f(f(x)), f(f(f(x))), ...
按照上述想法，我们可以设计一个程式接收函数 f 及猜想数值并不断迫近函数 f 的固定点。在程式中将不断应用函数 f，直到查找的结果变化小于预期限度即可。程式如下：
(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))我们可以将上述程式应用于下列实例：
(fixed-point cos 1.0)
.7390822985224023
(fixed-point (lambda (y) (+ (sin y) (cos y)))
1.0)
1.2587315962971173描述固定点的过程同样让我们回忆起之前计算平方根的内容。它们的相似之处在于通过优化猜想值迫近结果，我们也可以通过查找固定点的方式计算平方根。如果 x 为 y 的平方根则满足等式 ，等式可转换为
y=x/y，至此我们会发现计算平方根其实是在查找 的固定点。所以计算平方根的程式可以改写如下：
(define (sqrt x)
(fixed-point (lambda (y) (/ x y))
1.0))虽然看起来十分合理，但这种方式无法计算平方根。首先假设猜想值为 y1，下一个猜想值为 y2=x/y1，接着再下一个猜想值为 y3=x/y2=x/(x/y1)=y1。也就是说计算过程会陷入 y1 与 y2 的无限循环中，产生循环摆动的结果值。
不过可以通过一种方式摆脱这种循环摆动的情况。当结果处于 y 与 x/y 之间时可以通过计算平均值的方式创建一个新猜想值，也就是说 y 的下一个猜想值应该是 ，而计算平方根也就成为了查找
固定点的过程：
(define (sqrt x)
(fixed-point (lambda (y) (average y (/ x y)))
1.0))需要注意的是， 是通过在
y=x/y 左右同时加上 y 转换得到。
在上述修改后，计算平方根结果的程式便能正常运行。上述程式计算平方根产生的中间值序列与原先的平方根计算程式产生的中间值完全相同，这种通过连续平均值迫近结果的方式称为 平均阻尼（average damping），通常用于解决固定点问题。
前面章节的例子已经演示了将程式作为参数传递的能力，这有效增进了程序语言的表达能力，除此之外，也可以将程式作为参数返回，这也是编程语言表达能力的体现。
我们回看前面章节讲解的查找固定点例子，最后通过查找固定点的方法重新改写平方根计算程式，并且还使用平均阻尼的方式使计算平方根的程式得以可能。平均阻尼的数学解释为，给定数 x 和函数 f，x 与 f(x) 取平均的结果为平均阻尼，改写程式如下：
(define (average-damp f)
(lambda (x) (average x (f x))))average-damp 程式接收参数函数 f 并且返回一个程式作为结果，我们可以将返回结果应用于 x，得到 x 与 (f x) 的平均值。然后通过 average-damp 改写求平方根程式，如下：
(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y)))
1.0))上述程式包含了 3 个相关概念，分别是固定点查找、平均阻尼和 函数。此时回看最初的求平方根程式，虽然与现在的程式表达的过程未曾变化，但通过更加抽象概念的表达使程式本身表达的概念更加清晰。一般来说，将一个过程转换为程式有多种办法，经验丰富的程序员知道如何组合可以使程式更加易读，如何分离其中的元素进行复用。举个关于复用的例子，x 的立方根是函数
的固定点，所以我们可以立即按照平方根的程式创建一个立方根程式，如下：
(define (cube-root x)
(fixed-point (average-damp (lambda (y) (/ x (square y))))
1.0))其实最初求平方根的程式是牛顿法的一个特例。牛顿法的数学定义应该是，如果 是一个可以导函数，那么
g(x) = 0 的解就是 的固定点，如下表达式：
其中 Dg(x) 是函数 g 关于 x 的微分，可以看出牛顿法也使用了查找固定点的方式。
对于多数函数 g 只要有足够好的初始猜想值 x，便可以快速算出 g(x)=0 的解。
为了将牛顿法转换为程式，首先要描述微分的概念。微分与平均阻尼一样，会将一个函数转换为另一个函数。例如， 的微分结果为
。按照常规，如果 g 是一个函数，而 dx 是极小数时，函数 g 的微分 Dg 在任意数值 x 上的微分公式如下：
将微分概念转换为程式如下：
(define dx 0.00001)
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))与 average-damp 一样，deriv 也是一个将程式作为参数并返回程式的程式。例如，要逼近 在值为 5 时的微分结果，可以如下书写表达式：
(define (cube x) (* x x x))
((deriv cube) 5)
75.00014999664018运用 deriv 我们可以将牛顿法转换为如下程式：
(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))newton-transform 按本节开头的表述编写，newtons-method 则快速实现定义了牛顿法的计算。计算平方根按照牛顿法表述为 ，初始猜想值为 1。
它启示了我们另一种平方根程式的形式：
(define (sqrt x)
(newtons-method
(lambda (y) (- (square y) x)) 1.0))我们已经通过两种更加普适的方式表述了平方根的计算，一种是固定点查找，另一种是牛顿法。因为牛顿法也是一种固定点查找流程的表达，所以准确地说，我们实际上是使用了两种通过固定点计算平方根的方法。每种方法都以一个函数开始，然后查找转换后函数的固定点，可以将这个概念转换为下列程式：
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))这个通用程式的参数中包括转换 g 函数的程式，函数 g 及猜想值 guess，然后返回转换后函数的固定点作为结果。
按照这一级抽象，我们再改写本节的第一个平方根程式，改写后的程式如下：
(define (sqrt x)
(fixed-point-of-transform
(lambda (y) (/ x y)) average-damp 1.0))接着再改写第二个平方根程式，如下：
(define (sqrt x)
(fixed-point-of-transform
(lambda (y) (- (square y) x)) newton-transform 1.0))从本章内容中，我们发现程式的组合是一个更加关键的概念，因为这个概念可以帮助我们将计算的通用方法作为编程语言中的元素使用，而高阶程式运用通用方法完成更高阶的抽象。
作为程序员，我们应该选择识别程序底层的抽象，然后构建它们，运用它们创建更加强大的抽象概念。这并不是说要用最抽象的方式编写程序，而是应该像一名成熟的程序员一样，知道如何选择最适合当前任务的抽象层级。不过在术语中使用抽象概念思考十分重要，因为在新的场景中也可能使用到相同的抽象概念。高阶程式的重要意义在于可以将抽象作为编程语言中的具象元素使用，就如同操作其它语言中的元素一般。
通常编程语言会对可维护的可计算元素施加限制，而被施加限制最少的元素被称为 第一类（first-class） 状态。第一类元素拥有以下特权：
- 能够命名为变量
- 可以作为参数传递给程式
- 可以作为程式的结果返回
- 能够被包含在数据结构中
与其他熟知的编程语言不同，对于 Lisp 程式是它的第一类元素。虽然这对高效的语言实现提出了挑战，但它无疑获得了极强的表达能力。