第一章 构造抽象过程


1.1 程序设计的基本元素

为了让我们能通过程序语言组织自己有关计算过程的思想,每一种强有力的语言都提供了三种机制,使我们能够将简单的认识组合起来形成更复杂的认识:

  • 基本表达式,指语言中最基本的实体
  • 组合的方法,通过它们可以用简单元素构成复合元素
  • 抽象的方法,通过它们可以给复合元素命名,并将其视为单元操作

组合式求值有以下步骤:

  1. 对组合式的各个子表达式求值
  2. 将运算符的值应用于其它子表达式的值

对子表达式求值时也必须遵循这样的步骤,这意味着求值步骤本身就是递归的。

define 是我们给值命名的方式,也是最简单的抽象方式,形如 (define x 3) 。这样做会导致名字 x 与值 3 相关联。将名字与值相关联,又能根据名字提取出值,解释器需要存储空间来维护名字-值关联,这存储空间被称为环境

过程定义形如 (define (<name> <formal parameters>) <body>),将用对应的实际参数替换形式参数,再求值的这一过程,在环境中绑定给一个名字,便于以后的调用。

应用序求值正则序求值是表达式求值的两种方式。应用序求值时,解释器首先对运算符和各个对象求值,之后将得到的过程应用于得到的实际参数。而正则序求值时,先不求出运算对象的值,直到需要它们时再去求。

  • 应用序,概括为 “先求值而后应用”
  • 正则序,概括为 “完全展开后规约”

Lisp 采用应用序求值,部分原因在于这样做能避免对于表达式的重复求值,从而可以提高一些效率。更重要的是,在超出了可以采用代换方式模拟过程的范围后,正则序的处理将变得复杂得多。

条件表达式和谓词,形如

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

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

cond 之后跟随着形如 (<p> <e>) 的表达式,称为从句。从句中的 <p> 是谓词,与结果表达式 <e> 相对应。整个 cond 表达式的值是从左到右第一个谓词为真的从句的结果表达式,其中 else 是一个永远为真的谓词。

要对一个 if 表达式求值,首先对 <predicate> 求值。如果其为真,求出 <consequent> 的值,否则求出 <alternative> 的值作为整个 if 表达式的值。

由于 condif 不一定对其所有子表达式求值,它们不是一般的过程,而是特殊形式

形式参数叫什么名字,其实无所谓,这样的名字称为约束变量。如果一个变量不是被约束的,我们就称它为自由的。名字在其中被约束的表达式的集合称为名字的作用域。约束变量在将其作为形式参数的过程中的作用域是这个过程的过程体。

词法作用域是作用域的一种工作模型。内层过程中的自由变量,实际上是外围过程定义中的约束变量。

嵌套定义的过程,称为块结构。块结构的好处是,可以省去将某些变量在内层过程中传递的过程。

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

能够遇见所作所为的后果,是一种很重要的能力。

过程规定了计算状态如何从之前的计算状态演变而来。计算的具体行为很难捉摸,但我们可以找到演变的一般模式。从全局的角度判断计算状态的演变方式,这就是这一节所需要学习的内容。


递归过程递归计算是不同的概念:递归过程是指一个过程的定义中,包含了引用自身的表达式。而递归计算,指的是递归实际的演变方式。

线性递归线性迭代是计算的两种演变方式:

  • 线性递归:计算过程中不断展开表达式,随之构建起一条延迟操作的链,并在这些运算实际进行时收缩。当需要保存的信息量(正如延迟操作的步数)与问题规模的增长成正比时,称为线性递归。
  • 线性迭代:没有增长和收缩过程,需要保存的信息是一定数量的状态变量,并且用一套规则来指定状态变量的更新方式。当计算步数与问题规模的增长成正比时,称为线性迭代。

迭代过程中,状态变量完全描述了当前的状态,只要提供这些状态变量,计算就能随时进行下去;而递归过程就不同了,递归过程中记录了变量以外的额外信息,用于告诉解释器 “我们在延迟操作链上的什么位置”。

树形递归是指递归过程中多次引用自身,使 “延迟操作链” 分叉为树形结构。树形递归往往需要极多运算资源,但它不是无用的。处理有层级结构的数据时,树形递归是个自然而强大的工具;处理数字时,树形递归方式更容易理解。

对于树形递归的计算过程中的每一个节点,只需保存树中在其之上的节点的信息。一般来说,树形递归的计算所需的步骤数正比于树中的节点数,所需空间正比于树的最大深度。

(练习 3.27 介绍了如何用表格优化树形递归,先挖个坑)

增长阶为计算所需要的资源量,提供了粗略的估计。设 ${\rm R}(n)$ 为问题规模为 $n$ 时所需的计算资源量。当

$$\exists k_1,k_2,N\;\forall n>N\,(k_1f(n)\leq{\rm R}(n)\leq k_2f(n))$$

成立时,我们称 ${\rm R}(n)$ 有 $\Theta(f(n))$ 的增长阶,记作 ${\rm R}(n)\sim\Theta(f(n))$ 。

Lamé定理:如果用欧几里德算法计算一对数的 GCD 需要执行 $k$ 步,那么更小的那个数一定不小于第 $k$ 个斐波那契数。

运用这个定理,可以很方便地分析欧几里德算法的增长阶。设更小的数为 $n$,则一定有 $n\geq{\rm Fib}(k)\approx\frac{\phi^k}{\sqrt5}$ 。从此可以看出,$k$ 正比于 $\log_\phi(n)$ 增长,所以欧几里德算法的增长阶为 $\Theta(\log n)$ 。

费马小定理:若 $n$ 是素数,则对于任意 $a$ 不是 $n$ 的倍数,都有 $a^n\equiv a\;({\rm mod}\;n)$,它的另一个形式是 $a^{n-1}\equiv1\;({\rm mod}\;n)$,在$\text{Miller–Rabin}$素性测试中得以应用。

1.3 用高阶函数做抽象

为了增加描述能力,一门强大的语言需要:将共有的模式命名并建立抽象,而后直接在抽象的层次上工作。

这就需要引入高阶过程,它们以过程为参数,或者以过程为返回值。


将过程作为参数,或者将过程作为其值,以便用过程来处理过程,这样的过程称作高阶过程

匿名过程形如 (lambda (<formal-parameters>) <body>) 。lambdadefine 一样创造过程,但是不为它们绑定名称。

局部变量使用以下语法进行绑定,它们的作用域是 <body> 部分:

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>))
   <body>)

let 也是一种特殊形式,和调用过程时,将表达式的值绑定给形式参数的原理一样,它并没有引入新的机制。

“$\mapsto$” 这个符号叫做映射 $($$\textit{maps to}$$)$,是 lambda 在数学中的表达。例如 $y\mapsto x/y$ 可以被表达为 (lambda (y) (/ x y)) 。

一般来说,程序语言会对计算元素的可操作方式作出限制。而带有最少限制的元素被称为拥有第一级状态,这些元素有这些特点:

  • 可以被绑定给一个变量
  • 可以作为参数传递给一个过程
  • 可以被一个过程作为返回值
  • 可以存储在数据结构中

Lisp 语言为过程赋予了完全的第一级状态,由此获得的描述能力是惊人的。

这样做是有代价的,也为解释器的实现提出了挑战:实现第一级状态的过程需要为过程中的自由变量预留存储空间,即使某个过程并没有被调用。

Comments