第 7 章 附录：Scheme

这里我们给出 Scheme 的基础入门介绍。关于该语言的更精确解释，请参见 IEEE 标准 [24]；更长的介绍见教材 [1]。

Scheme 是一种基于表达式的简单编程语言。表达式命名了一个值。例如，数字 3.14 命名了一个熟悉数的近似值。既有基本表达式（如数字）可以直接识别，也有多种类型的复合表达式。

过程调用

过程调用（procedure call）是一种复合表达式。过程调用是用括号分隔的一系列表达式。过程调用中的第一个子表达式被认为命名了一个过程，其余的子表达式被认为命名了该过程的参数。过程应用于给定参数时所产生的值，即为该过程调用所命名的值。例如，

(+ 1 2.14)
3.14

(+ 1 (* 2 1.07))
3.14

这两个复合表达式都命名了与数字 3.14 相同的数。2 在这些例子中，符号 + 和 * 分别命名了执行加法和乘法的过程。如果我们用命名相同事物的表达式替换任何表达式中的任何子表达式，则整个表达式所命名的事物保持不变。一般来说，过程调用写作

( operator operand-1 ... operand-n )

其中 operator 命名了一个过程，operand-i 命名了第 i 个实参。3

Lambda 表达式

正如我们使用数字来命名数一样，我们使用 表达式来命名过程。4 例如，对其输入求平方的过程可以写作：

(lambda (x) (* x x))

这个表达式可以读作：“一个参数 x 的过程，该过程将 x 乘以 x。”当然，我们可以在任何需要过程的上下文中使用此表达式。例如，

((lambda (x) (* x x)) 4)
16

一个 表达式的一般形式为

(lambda formal-parameters body)

其中 formal-parameters 是符号列表，这些符号将是过程参数的名字；而 body 是一个可能引用这些形式参数的表达式。过程调用的值就是将实参代入形式参数后，过程体（body）的值。

定义

我们可以使用 define 结构为任何对象赋予名称。例如，如果我们做出以下定义5

(define pi 3.141592653589793)

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

之后我们就可以在任何可以使用数字或 表达式的地方使用符号 pi 和 square。例如，半径为 5 米的球体表面积为

(* 4 pi (square 5))
314.1592653589793

过程的定义可以使用“语法糖”更方便地表示。平方过程可以定义为

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

我们可以读作：

在 Scheme 中，过程可以作为参数传递，也可以作为返回值返回。例如，可以实现一个表示数学中函数复合（composition）概念的过程：6

(define compose
  (lambda (f g)
    (lambda (x)
      (f (g x)))))

((compose square sin) 2)
.826821810431806

(square (sin 2))
.826821810431806

使用上面展示的语法糖，我们可以更方便地编写该定义。以下两种写法都与上面的定义等价：

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define ((compose f g) x)
  (f (g x)))

条件表达式

条件表达式可用于在多个表达式之间进行选择以产生一个值。例如，实现绝对值函数的过程可以写作：

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) x)
        ((> x 0) x)))

条件表达式 cond 接受若干子句。每个子句包含一个谓词表达式（可为真或假）和一个结果表达式。cond 表达式的值是第一个对应谓词表达式为真的子句的结果表达式的值。条件表达式的一般形式为

(cond (predicate-1 consequent-1)
      ···
      (predicate-n consequent-n))

为了方便，有一个特殊的谓词表达式 else 可以用作 cond 最后一个子句的谓词。当只有二选一时，if 结构提供了另一种实现条件表达式的方式。例如，因为只有参数为负时才需要做特殊处理，我们可以将 abs 定义为：

(define (abs x)
  (if (< x 0)
      (- x)
      x))

if 表达式的一般形式为

(if predicate consequent alternative)

如果谓词为真，则 if 表达式的值是结果表达式（consequent）的值，否则是备选表达式（alternative）的值。

递归过程

有了条件表达式和定义，我们就可以编写递归过程了。例如，要计算第 n 个阶乘数，可以写作：

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
(factorial 6)
720

(factorial 40)
815915283247897734345611269596115894272000000000

局部名称

let 表达式用于在局部上下文中为对象命名。例如，

(define (f radius)
  (let ((area (* 4 pi (square radius)))
        (volume (* 4/3 pi (cube radius))))
    (/ volume area)))

(f 3)
1

let 表达式的一般形式为

(let ((variable-1 expression-1)
      ···
      (variable-n expression-n))
  body)

let 表达式的值是在变量 variable-i 具有表达式 expression-i 值的上下文中，body 表达式的值。表达式 expression-i 不能引用任何变量。

let 表达式的一个轻微变体提供了一种方便的方式来表达循环结构。我们可以编写一个实现阶乘替代算法的过程如下：

(define (factorial n)
  (let factlp ((count 1) (answer 1))
    (if (> count n) 
        answer
        (factlp (+ count 1) (* count answer)))))

(factorial 6)
720

在这里，let 之后的符号 factlp 被局部定义为一个过程，其形式参数为变量 count 和 answer。它首次被调用时使用表达式 1 和 1，以此初始化循环。每当之后调用名为 factlp 的过程时，这些变量获得的新值分别是操作数表达式 (+ count 1) 和 (* count answer) 的值。

复合数据——列表与向量

数据可以粘合在一起形成复合数据结构。列表（list）是一种元素按顺序链接的数据结构。Scheme 向量（vector）是一种元素按线性数组排列的数据结构。可以向列表中添加新元素，但访问列表的第 n 个元素所需的计算时间与 n 成正比。相比之下，Scheme 向量的长度是固定的，其元素可以在常数时间内访问。本书中的所有数据结构都是列表和 Scheme 向量的组合实现。复合数据对象由称为构造器（constructor）的过程构建其组成部分，并通过选择器（selector）访问这些组成部分。

过程 list 是列表的构造器。选择器 list-ref 用于获取列表的元素。Scheme 中的所有选择器都是从零开始索引的。例如，

(define a-list (list 6 946 8 356 12 620))

a-list
(6 946 8 356 12 620)

(list-ref a-list 3)
356

(list-ref a-list 0)
6

列表由序对（pair）构建而成。序对使用构造器 cons 创建。访问序对两个组成部分的选择器分别是 car 和 cdr（读作“could-er”）。7 列表是一串序对，其中每个序对的 car 是列表元素，每个序对的 cdr 是下一个序对，最后一个 cdr 是一个可区分的值，称为空列表（empty list），写作 ()。因此，

(car a-list)
6

(cdr a-list)
(946 8 356 12 620)

(car (cdr a-list))
946
(define another-list
  (cons 32 (cdr a-list)))

another-list
(32 946 8 356 12 620)
(car (cdr another-list))
946

a-list 和 another-list 共享相同的尾部（即它们的 cdr）。

有一个谓词 pair?，它对序对（pair）返回真，对所有其他类型的数据返回假。

向量比列表更简单。有一个构造器 vector 可以用来创建向量，还有一个选择器 vector-ref 用于访问向量的元素：

(define a-vector
  (vector 37 63 49 21 88 56))

a-vector
#(37 63 49 21 88 56)
(vector-ref a-vector 3)
21

(vector-ref a-vector 0)
37

注意，向量在打印输出时与列表的区别在于左括号前有一个字符 #。

有一个谓词 vector?，它对向量返回真，对所有其他类型的数据返回假。

列表和向量的元素可以是任何类型的数据，包括数字、过程、列表和向量。更多用于操作列表结构和向量结构数据的其他过程，请参见 Scheme 在线文档。

符号

符号（symbol）是一种非常重要的基本数据类型，我们用它来构造程序和代数表达式。你可能已经注意到，Scheme 程序看起来就像列表。实际上，它们就是列表。组成程序的列表中的一些元素是符号，例如 + 和 vector。如果我们要编写能够操作程序的程序，就需要能够写出命名此类符号的表达式。这通过引号（quotation）机制实现。符号 + 的名称是表达式 '+，一般来说，一个表达式的名称就是该表达式前加一个单引号字符。因此，表达式 (+ 3 a) 的名称是 '(+ 3 a)。

我们可以使用谓词 eq? 来测试两个符号是否相同。例如，我们可以编写一个程序来判断一个表达式是否为求和式：

(define (sum? expression)
  (and (pair? expression)
       (eq? (car expression) '+)))

(sum? '(+ 3 a))
#t

(sum? '(* 3 a))
#f

这里 #t 和 #f 分别是布尔值真（true）和假（false）的打印表示。

考虑如果我们在表达式 (sum? '(+ 3 a)) 中省略引号会发生什么。如果变量 a 的值为 4，那么我们就是在问 7 是否是一个求和式。但我们想知道的是表达式 (+ 3 a) 是否是一个求和式。这就是为什么我们需要引号。