Scheme 编程语言(2)启程

Scheme 编程语言(2)启程

Translator: Once Day date:2022年10月23日

漫漫长路有人对你微笑过吗…

仅供学习交流之用，请尊重原书版权。

原书：《The Scheme Programming Language, Fourth Edition》，R. Kent Dybvig.

原书章节: The Scheme Programming Language : Chapter 2.Getting Start.

这是一个学习的过程，不断修改和完善，供自己日后复习，水平有限，自娱自乐。

为了让读者也有独立思考的过程，所以一些疑难点就不添加注解，如果有疑问，欢迎留言，大家一起探讨。

（机翻文档，兼带修改。私人笔记，切莫多言）

2.开始(Getting Started)

本章是对Scheme语言的新手的介绍。如果您坐在交互式Scheme系统前，一边使用示例，一边尝试，您将从本章学到更多的知识。

在阅读本章并完成练习之后，您应该能够开始使用Scheme。您将了解Scheme程序的语法和它们的执行方式，以及如何使用简单的数据结构和控制机制。

2.1 与Scheme交流

大多数Scheme系统提供了交互式编程环境，简化了程序开发和测试。与Scheme最简单的交互遵循“读取-计算-打印(read-evaluate-print)”循环。一个程序(通常称为read-evaluate-print循环，或REPL)读取您在键盘上键入的每个表达式，对其求值然后打印其值。

使用交互式Scheme系统，您可以在键盘上输入一个表达式并立即看到它的值。您可以定义一个过程，并输入参数来调用它，以查看它是如何工作的。您甚至可以输入由一组“过程定义”组成的整个程序，并在不离开（交互式Scheme）系统的情况下对其进行测试。当程序开始变长时，将其输入到文件(使用文本编辑器)、然后加载文件并进行交互测试将更加方便。在大多数Scheme系统中，可以使用非标准过程load加载文件，该过程使用一个文件路径字符串作为参数。在文件中编写程序有几个好处:

• 你有机会更仔细地编写程序。
• 你可以在不重新输入程序的情况下纠正错误。
• 你可以保留一份副本供以后使用。

大多数Scheme实现对从文件中加载的表达式与在键盘上键入的表达式一视同仁。

Scheme提供各种输入和输出过程，而REPL负责读取表达式并打印表达式的值。这使您可以集中精力编写程序，而不必担心结果将如何显示。

本章和本书其余部分的例子遵循常规格式。首先给出您可能从键盘输入的表达式，也许跨越几行。表达式的值在==>之后给出，可看为“求值”。对于定义或者未指定值的表达式，则==>会被省略掉。

示例程序以一种“看起来不错”的风格来格式化，并清楚地表示程序的结构。代码很容易阅读，因为每个表达式及其子表达式之间的关系都清楚地显示了出来。注意，Scheme忽略缩进和换行，因此不需要遵循特定的样式来缩进和换行。重要的是要建立一种风格并坚持下去。Scheme将每个程序看成一行文本，其子表达式以从左到右的顺序分布。

如果您可以访问交互式Scheme系统，那么现在启动它并在阅读本书时输入示例可能是个好主意。最简单的Scheme表达式之一是字符串常量。试着输入“Hi，Mom!”(包括双引号)来响应提示符。系统应该回复“Hi，Mom!”。任何常数的值就是常数本身。

"Hi Mom!" ==> "Hi Mom!"

下面是一组表达式，每个表达式都有Scheme的响应(输出)。它们将在本章后面的章节中进行解释，但是现在使用它们来练习与Scheme的交互。

"hello" ==> "hello"
42 ==> 42
22/7 ==> 22/7
3.141592653 ==> 3.141592653
+ ==> #
(+ 76 31) ==> 107
(* -12 10) ==> -120
'(a b c d) ==> (a b c d)

注意不要漏掉任何单引号'、双引号""或括号()。如果您在最后一个表达式中遗漏了一个单引号，那么您可能会收到一条消息，提示发生了异常。可以试一下这种异常情况。如果您没有使用右括号或双引号，系统可能仍然在等待它。

这里还有一些可以尝试一下的表达式。你可以试着自己弄清楚它们是什么意思，或者等着在本章后面找到答案。

(car '(a b c)) ==> a
(cdr '(a b c)) ==> (b c)
(cons 'a '(b c)) ==> (a b c)
(cons (car '(a b c))(cdr '(d e f))) ==> (a e f)

正如您所看到的，Scheme表达式可能跨越不止一行。Scheme系统通过匹配双引号和圆括号知道它何时拥有完整的表达式。

接下来，让我们尝试定义一个过程。

(define square(lambda (n)(* n n)))

平方过程计算任意数n的平方 n 2 n^2 n2。我们将在本章后面详细介绍构成这个定义的表达式。现在，只需理解define建立"绑定变量"(variable bindings)，lambda创建过程，而*代表乘法过程就足够了。注意这些表达的形式。所有结构化的形式(structured forms)都用圆括号括起来，用前缀表示法写(prefix notation, 类似波兰前缀式)，也就是说，运算符在实参前面。如您所见，即使对于简单的算术运算(如*)也是如此。

尝试使用一下square这个过程。

(square 5) ==> 25
(square -200) ==> 40000
(square 0.5) ==> 0.25
(square -1/2) ==> 1/4

即使下面这个定义很短，您也可以将它输入到文件中。让我们假设您将该文件称为“reciprocal .ss”。

(define reciprocal(lambda (n)(if (= n 0)"oops!"(/ 1 n))))

这个过程是求倒数reciprocal，计算任意n ≠ 0时的1/n。当n = 0时，reciprocal返回字符串"oops!"。返回到Scheme，并尝试使用过程load加载文件。

(load "reciprocal.ss")

最后，尝试使用我们刚刚定义的过程。

(reciprocal 10) ==> 1/10
(reciprocal 1/10) ==> 10
(reciprocal 0) ==> "oops!"
(reciprocal (reciprocal 1/10)) ==> 1/10

在下一节中，我们将更详细地讨论Scheme表达式。在本章中，请记住Scheme系统是学习Scheme最有用的工具之一。无论何时，当你尝试文章中的一个例子时，都要用你自己的例子来补充学习。在交互式Scheme系统中，尝试某些东西的成本相对较小——通常只是输入它的时间。

2.2 简单表达式(Simple Expressions)

最简单的Scheme表达式是常量数据对象，如字符串、数字、符号(symbol)和列表(list)。Scheme支持其他对象类型，但是这四种类型对于许多程序来说已经足够了。在上一节中，我们看到了一些字符串和数字的例子。

让我们更详细地讨论一下数字。数字是常数。如果您输入一个数字，Scheme将向您返回该数字。下面的示例显示Scheme支持几种类型的数字。

123456789987654321 ==> 123456789987654321
3/4 ==> 3/4
2.718281828 ==> 2.718281828
2.2+1.1i ==> 2.2+1.1i

Scheme数包括精确整数、不精确整数、有理数、实数和复数。精确整数和有理数具有任意的精度，也就是说，它们的大小可以是任意的。不精确的数字通常在内部使用IEEE标准浮点数表示。

Scheme使用+、-、*和/来命名相应的算数过程。每个过程接受两个数值参数。下面的表达式称为过程应用(Procedure applications)，因为它们指定一个过程去应用在一组参数上。

(+ 1/2 1/2) ==> 1
(- 1.5 1/2) ==> 1.0(* 3 1/2) ==> 3/2
(/ 1.5 3/4) ==> 2.0

Scheme甚至对常见的算术运算也使用前缀表示法。任何过程应用，无论该过程接受0个、1个、2个还是多个参数，都被写成(procedure arg …)。这种规则简化了表达式的语法。无论操作是什么，都使用一种表示法，并且没有关于操作符优先级或结合性的复杂规则。

过程应用可能是嵌套的，在这种情况下，首先计算最里面的值。因此，我们可以把上面给出的算术程序嵌套应用到计算更复杂的公式中去。

(+ (+ 2 2) (+ 2 2)) ==> 8
(- 2 (* 4 1/3)) ==> 2/3
(* 2 (* 2 (* 2 (* 2 2)))) ==> 32
(/ (* 6/7 7/2) (- 4.5 1.5)) ==> 1.0

这些示例演示了使用Scheme作为四则运算桌面计算器所需的所有内容。虽然我们不在本章中讨论它们，但Scheme支持许多其他算术过程。现在是时候翻到第6.4节，尝试一下其中的一些方法了。

对于许多任务来说，简单的数值对象就足够了，但有时需要包含两个或多个值的聚合数据结构。在许多语言中，基本的聚合数据结构是数组(array)。在Scheme中，它是列表(list)。列表被写成用圆括号括起来的对象序列。例如，(1 2 3 4 5)是一个数字列表，("this" "is" a" "list")是一个字符串列表。列表不需要只包含一种类型的对象，因此(4.2 "hi")是一个包含数字和字符串的有效列表。列表可以嵌套(可以包含其他列表)，因此((1,2)(3 4))是一个包含两个元素的有效列表，每个元素都是一个含有两个元素的列表。

您可能会注意到列表看起来就像过程应用，想知道Scheme如何区分它们。也就是说，Scheme如何区分对象列表(obj1 obj2 …)和过程应用(procedure arg … )?

在某些情况下，这种区别似乎很明显。数字列表(1 2 3 4 5)很难与过程应用混淆，因为1是一个数字，而不是一个过程。因此，答案可能是Scheme查看列表或过程应用的第一个元素，并根据第一个元素是否为过程(procedure)做出决定。这个答案不够好，因为我们甚至有可能想把(+ 3 4)这样的有效过程应用(procedure application)当作一个列表。答案是，我们必须显式地告诉Scheme将列表视为数据，而不是过程应用。我们用quote过程来表示。

(quote (1 2 3 4 5)) ==> (1 2 3 4 5)
(quote ("this" "is" "a" "list")) ==> ("this" "is" "a" "list")
(quote (+ 3 4)) ==> (+ 3 4)

quote强制将列表作为数据处理。试着输入上面没有quote的表达式。您可能会收到一条消息，指示前两个表达式出现了异常，第三个表达式出现了错误的答案(7)。

因为在Scheme代码中经常需要quote，所以Scheme将表达式前面的单引号(')识别为quote的缩写。

'(1 2 3 4) ==> (1 2 3 4)
'((1 2) (3 4)) ==> ((1 2) (3 4))
'(/ (* 2 -1) 3) ==> (/ (* 2 -1) 3)

这两种形式都被称为引号表达式(quote expressions)。当一个对象被括在一个引号表达式中时，我们通常说它被引用了。

引号(quote)表达式不是过程应用，因为它禁止对其子表达式求值。这是一种完全不同的语法形式。除了过程应用和引号表达式外，Scheme还支持其他几种语法形式。每个语法形式的计算方法都不同。幸运的是，不同的语法形式其数量很少。我们将在本章后面看到更多。

并不是所有的引号表达式涉及到列表。尝试使用以下带有或不带有quote包装的表达式。

(quote hello) ==> hello

符号hello必须加quote，以防止Scheme将hello作为变量处理。Scheme中的符号和变量类似于数学表达式和方程中的符号和变量。当我们求数学表达式1 - x的某值时，我们认为x是一个变量。另一方面，当我们考虑代数方程x2 - 1 = (x - 1)(x + 1)时，我们认为x是一个符号(事实上，我们认为整个方程是象征性的)。正如引用一个列表告诉Scheme将括号表达式(parenthesized form)作为列表而不是过程应用一样，引用一个标识符也告诉Scheme将标识符作为符号而不是变量。虽然符号通常用于指代方程或程序中的符号形式变量(variables in symbolic representations)，但符号也可以用作表示自然语言句子的单词。

您可能想知道为什么(过程)应用、变量与列表、符号共享一套表示方法。共享表示方法允许将Scheme程序看作为Scheme数据，从而简化了解释器、编译器、编辑器和Scheme中其他工具的编写。12.7节中给出的Scheme解释器演示了这一点，它本身是用Scheme编写的。许多人认为这是Scheme中最重要的特色之一。

数字和字符串也可以被引用。

'2 ==> 2
'2/3 ==> 2/3
(quote "Hi Mom!") ==> "Hi Mom!"

然而，数字和字符串在任何情况下都被视为常量，因此没有必要引用(quote)它们。

现在，让我们讨论一些用于操作列表的Scheme过程。分解列表有两个基本过程: car和cdr(发音为could-er)。car返回列表的第一个元素，cdr返回列表的其余部分。名称“car”和“cdr”源自实现Lisp语言的第一台计算机IBM 704所支持的操作。每个操作都需要一个非空列表作为参数。

(car '(a b c)) ==> a
(cdr '(a b c)) ==> (b c)
(cdr '(a)) ==> ()(car (cdr '(a b c))) ==> b
(cdr (cdr '(a b c))) ==> (c)(car '((a b) (c d))) ==> (a b)
(cdr '((a b) (c d))) ==> ((c d))

列表的第一个元素通常被称为列表的“car”，列表的其余部分通常被称为列表的“cdr”。只有一个元素的列表的cdr是()，即空列表。

过程cons构造列表，它有两个参数。第二个参数”通常“是一个列表，在这种情况下，cons返回一个列表。

(cons 'a '()) ==> (a)
(cons 'a '(b c)) ==> (a b c)
(cons 'a (cons 'b (cons 'c '()))) ==> (a b c)
(cons '(a b) '(c d)) ==> ((a b) c d)(car (cons 'a '(b c))) ==> a
(cdr (cons 'a '(b c))) ==> (b c)
(cons (car '(a b c))(cdr '(d e f))) ==> (a e f)
(cons (car '(a b c))(cdr '(a b c))) ==> (a b c)

就像“car”和“cdr”经常被用作名词一样，“cons”经常被用作动词。通过向列表的开头添加元素来创建新列表的方法称为将元素插入到列表上(consing the element onto the list)。

注意在对cons第二个参数描述中的”通常“这个词。过程cons实际上构建了序对(pairs)，而且没有理由认为序对的cdr必须是一个列表。列表是由序对组成的一个序列，每一个序对的cdr都是序列中对应位置的下一个序对。

规则列表(proper list)中最后一个序对的cdr为空列表。否则，序对组成的序列就会形成一个非规则列表(improper list)。更正式地说，空列表"'()"是一个规则列表，任何cdr是一个规则列表的序对都是一个规则列表。

非规则列表以点对表示法(dotted-pair notation)打印，在列表的最后一个元素前面有一个句号或小数点。

(cons 'a 'b) ==> (a . b)
(cdr '(a . b)) ==> b
(cons 'a '(b . c)) ==> (a b . c)

由于它的打印格式，cdr不是列表的序对通常被称为点对(dotted pair)。然而，即使是cdr是列表的序对也可以用点对表示法书写，不过对于规则列表，其总是输出不带点dot格式的文本。

'(a . (b . (c . ()))) ==> (a b c)

过程list与cons类似，不同之处在于它接受任意数量的参数，并且总是构建一个规则列表。

(list 'a 'b 'c) ==> (a b c)
(list 'a) ==> (a)
(list) ==> ()

第6.3节提供了更多关于列表和操作它们的Scheme过程的信息。这可能是跳到那一节并熟悉那里给出的其他过程的好时机。

练习题 2.2.1

Convert the following arithmetic expressions into Scheme expressions and evaluate them.

将下面的算术表达式转换成Scheme表达式，然后对它们求值。

 a.	1.2 × (2 - 1/3) + -8.7b.	(2/3 + 4/9) ÷ (5/11 - 4/3)c.	1 + 1 ÷ (2 + 1 ÷ (1 + 1/2))d.	1 × -2 × 3 × -4 × 5 × -6 × 7

练习题 2.2.2

Experiment with the procedures +, -, *, and / to determine Scheme’s rules for the type of value returned by each when given different types of numeric arguments.

对+,-,*和/过程进行测试，以确定在给定不同类型的数值参数时，对于每个过程返回值的类型，Scheme所采用的规则。

练习题 2.2.3

Determine the values of the following expressions. Use your Scheme system to verify your answers.

确定以下表达式的值。使用Scheme系统验证您的答案。

 a.	(cons 'car 'cdr)b.	(list 'this '(is silly))c.	(cons 'is '(this silly?))d.	(quote (+ 2 3))e.	(cons '+ '(2 3))f.	(car '(+ 2 3))g.	(cdr '(+ 2 3))h.	consi.	(quote cons)j.	(quote (quote cons))k.	(car (quote (quote cons)))l.	(+ 2 3)m.	(+ '2 '3)n.	(+ (car '(2 3)) (car (cdr '(2 3))))o.	((car (list + - * /)) 2 3)

练习题 2.2.4

(car (car '((a b) (c d)))) yields a. Determine which compositions of car and cdr applied to ((a b) (c d)) yield b, c, and d.

给出的表达式生成了a的值，确定其他car和cdr的组合，来分别生成b，c，d的值。

练习题 2.2.5

Write a Scheme expression that evaluates to the following internal list structure.

编写一个Scheme表达式，计算结果为具有以下内部结构的列表。

（onceday注: 一种参考实现(list (cons 'a 'b) '((c) (d)) '(())) ==> ((a . b) ((c) (d)) (())))

练习题 2.2.6

Draw the internal list structure produced by the expression below.

绘制由下面的表达式生成的内部列表结构。

(cons 1 (cons '(2 . ((3) . ())) (cons '(()) (cons 4 5))))

练习题 2.2.7

The behavior of (car (car (car '((a b) (c d))))) is undefined because (car '((a b) (c d))) is (a b), (car '(a b)) is a, and (car 'a) is undefined. Determine all legal compositions of car and cdr applied to ((a b) (c d)).

给出了一种取值未定义的car和cdr组合(非法组合)，那么对于((a b) (c d))，其合法的car和cdr组合有哪些.

练习题 2.2.8

Try to explain how Scheme expressions are evaluated. Does your explanation cover the last example in Exercise 2.2.3?

试着解释如何计算Scheme表达式。你能解释练习题2.2.3中的最后一个例子吗?

（onceday注: 过程即数据)

2.3 求值Scheme表达式

让我们讨论Scheme如何计算您键入的表达式。我们已经为常量对象(如字符串和数字)建立了规则:对象本身就是值。您可能还在脑海中制定了一个规则，用于对表达式(procedure arg1 ... argn)求值。这里，procedure代表一个Scheme过程，arg1 ... argn是表示其参数的表达式。一种可能性如下:

• 找到procedure的值
• 找到arg1的值
• …
• 找到arg2的值
• 将过程procedure的值应用到arg1 ... arg2的值之上

例如，考虑简单的”过程应用“(+ 3 4)。+的值是加法过程，3的值是数字3，4的值是数字4。对3和4应用加法过程得到7，因此我们的值是对象7。

通过在每一层级应用上述过程，我们可以求取嵌套表达式的值(* (+ 3 4) 2)。*的值是乘法过程，(+ 3 4)的值可以确定为数字7，2的值是数字2。7乘以2得到14，所以答案是14。

此规则适用于过程应用，但不适用于引号表达式(quote ...)，因为过程应用的子表达式会求值，而引号表达式的子表达式则不会求值。引号表达式的求值更类似于常量对象的求值。具有(quote object)形式的引用表达式其值就是简单的object。

常量对象、过程应用和引号表达式只是Scheme提供的众多语法形式中的三种。幸运的是，Scheme程序员只需要直接理解少数的语法形式，这些被称为核心语法形式。其余的语法形式归根到底是根据核心语法形式定义的语法扩展。我们将在本章的其余部分讨论其余的核心语法形式和一些语法扩展。3.1节总结了核心句法形式，并介绍了句法扩展机制。

在我们继续讨论更多语法形式和过程之前，值得注意与过程应用求值有关的两点。首先第一点，上面给出的过程被过度指定了，因为它要求从左到右计算子表达式。也就是说，procedure在arg1之前求值，arg1在arg2之前求值，以此类推。但实际情况不一定是这样。Scheme计算器可以自由地以任何顺序计算表达式，如从左到右、从右到左或任何其他顺序。事实上，对于不同的过程应用，子表达式可能以不同的顺序求值，甚至在相同的实现中也是如此。

第二点是procedure的计算方法与arg1 ... argn 一样。虽然procedure通常是一个命名特定过程的变量，但并不一定都是这样。练习2.2.3让您确定表达式((car (list + - * /)) 2 3)的值。这里的过程是(car (list + - * /))。(car (list + - * /))的值是加法过程，就好像procedure只是变量+一样。

练习题 2.3.1

Write down the steps necessary to evaluate the expression below.

写出计算下面表达式所需的步骤。

((car (cdr (list + - * /))) 17 5)

2.4 变量和Let表达式

假设expr是一个包含变量var的Scheme表达式。另外，假设在计算expr时，我们希望var的值为val。例如，当求值(+ x 3)时，我们可能希望x的值为2。或者，当求值(+ 2 y)时，我们可能希望y的值为3。下面的示例演示如何使用Scheme的let语法形式实现这一点。

(let ((x 2))(+ x 3)) ==> 5(let ((y 3))(+ 2 y)) ==> 5(let ((x 2) (y 3))(+ x y)) ==> 5

let语法形式包括一个由序对(变量 表达式)组成的列表，以及称为let主体的表达式序列。let表达式的一般形式如下:

(let ((var expr) ...) body1 body2 ...)

我们说变量通过let绑定到值上。我们将由let绑定的变量称为let绑定变量(let-bound variables)。

let表达式通常用于简化包含两个相同子表达式的表达式。这样做还确保只计算一次相同子表达式的值。

(+ (* 4 4) (* 4 4)) ==> 32
(let ((a (* 4 4))) (+ a a)) ==> 32

方括号通常用来代替圆括号来分隔let表达式的变量绑定。

(let ([list1 '(a b c)] [list2 '(d e f)])(cons (cons (car list1)(car list2))(cons (car (cdr list1))(car (cdr list2))))) ==> ((a . d) b . e)

Scheme对待方括号内的表达式就像圆括号内的表达式一样。一个开始方括号必须与一个结束方括号匹配，一个开始圆括号必须与一个结束圆括号匹配。我们使用方括号来表示let绑定变量(以及其他几种标准语法形式)，以提高可读性，特别是当我们可能有两个或多个连续的开始圆括号时。

由于位于过程应用第一个位置的表达式的计算方法与其他表达式没有区别，所以也可以在那里使用let绑定变量。

(let ([f +])(f 2 3)) ==> 5(let ([f +] [x 2])(f x 3)) ==> 5(let ([f +] [x 2] [y 3])(f x y)) ==> 5

由let绑定的变量仅在let的主体中可见。

(let ([+ *])(+ 2 3)) ==> 6(+ 2 3) ==> 5

这是幸运的，因为我们不希望+的值在任何地方都是乘法过程。嵌套使用let表达式也是可以的。

(let ([a 4] [b -3])(let ([a-squared (* a a)][b-squared (* b b)])(+ a-squared b-squared))) ==> 25

当嵌套的let表达式绑定相同的变量时，只有内部let创建的绑定在其主体中是可见的。

(let ([x 1])(let ([x (+ x 1)])(+ x x))) ==> 4

外部的let表达式在主体内将x绑定到1，其主体是第二个let表达式。内部的let表达式在它的主体中将x绑定到(+ x 1)，其主体也就是表达式(+ x x)。(+ x 1)的值是多少? 由于(+ x 1)出现在外部的let主体中，但不在内部的let主体中，所以此x的值必须为1，而(+ x 1)的值为2。(+ x x)呢? 它出现在两个let表达式的主体中。但只有最内层的绑定x是可见的，所以x是2，(+ x x)是4。

内部绑定的x可认为屏蔽了外部绑定的x。let绑定变量在它的let表达式主体内除了被屏蔽的地方外，其他任何地方都是可见的。绑定变量可见的区域称为作用域(scope)。在上面的例子中，第一个x的作用域是外部let表达式的主体减去内部let表达式的主体，因为在内部let表达式主体中它被第二个x遮蔽。这种形式的作用域称为词法作用域(lexical scoping)，因为每个绑定变量的作用域可以直接通过对程序的文本分析确定。

可以通过为变量选择不同的名称来避免屏蔽(Shadowing)。上面的表达式可以重写，使内部let绑定的变量为new-x。

(let ([x 1])(let ([new-x (+ x 1)])(+ new-x new-x)))  4

虽然选择不同的名称有时可以防止混淆，但屏蔽(shadowing)可以帮助防止意外使用“旧”值。例如，在前面示例的原始版本中，我们不可能在内部let的主体中错误地引用外部x。

练习题 2.4.1

Rewrite the following expressions, using let to remove common subexpressions and to improve the structure of the code. Do not perform any algebraic simplifications.

重写下面的表达式，使用let删除公共子表达式并改进代码的结构。不要进行任何代数化简。

 a.	(+ (- (* 3 a) b) (+ (* 3 a) b))b.	(cons (car (list a b c)) (cdr (list a b c)))

练习题 2.4.2

Determine the value of the following expression. Explain how you derived this value.

确定以下表达式的值。解释一下你是如何得出这个值的。

(let ([x 9])(* x(let ([x (/ x 3)])(+ x x))))

练习题 2.4.3

Rewrite the following expressions to give unique names to each different let-bound variable so that none of the variables is shadowed. Verify that the value of your expression is the same as that of the original expression.

重写下面的表达式，为每个不同的let绑定变量提供惟一的名称，以便没有一个变量被遮蔽。验证表达式的值是否与原始表达式的值相同。

a.	(let ([x 'a] [y 'b])(list (let ([x 'c]) (cons x y))(let ([y 'd]) (cons x y))))b.	(let ([x '((a b) c)])(cons (let ([x (cdr x)])(car x))(let ([x (car x)])(cons (let ([x (cdr x)])(car x))(cons (let ([x (car x)])x)(cdr x))))))

2.5 Lambda 表达式

在表达式(let ([x (* 3 4)]) (+ x x))中，变量x被绑定到(* 3 4)的值。如果我们对于(+ x x)表达式，想要其中x被绑定到(/ 99 11)的值, 或者与(- 2 7)的值绑定在一起, 该怎么办呢? 在每种情况下，我们都需要不同的let表达式。然而，当let的主体部分很复杂时，必须重复(使用相同的表达式)是很不方便的。

相反，我们可以使用语法形式lambda来创建一个以x作为参数并具有与let表达式相同主体的新过程。

(lambda (x) (+ x x)) ==> #

Lambda表达式的通用形式如下：

(lambda (var ...) body1 body2 ...)

变量var ...是程序的形式参数(formal parameters)，表达式的序列body1 body2 ...是它的主体。(实际上，真正的一般形式比这更一般，稍后您会看到。)

过程与数字、字符串、符号或序对一样都是对象。然而，就Scheme而言，过程没有任何有意义的打印形式，因此本书使用符号说明表达式的值是一个过程。

对过程执行的最常见操作是将其应用(apply)于一个或多个值。

((lambda (x) (+ x x)) (* 3 4)) ==> 24

这与任何其他过程应用没有区别。该过程是(lambda (x) (+ x x))的值，唯一的参数是(* 3 4)或12的值。实参值或实参(actual parameters)被绑定到lambda表达式中的形参(formal parameters)，其方法与let绑定变量绑定它们的值相同。在本例中，x被绑定为12，(+ x x)的值为24。因此，将该过程应用于值12的结果是24。

因为过程是对象，我们可以将过程作为变量的值，并多次使用该过程。

(let ([double (lambda (x) (+ x x))])(list (double (* 3 4))(double (/ 99 11))(double (- 2 7)))) ==> (24 18 -10)

在这里，我们把double绑定到一个过程，然后使用这个过程对三个不同的值进行翻倍处理。

这个过程期望它的实参是一个数字，因为它将实参传递给+。通常，实际的参数可以是任何类型的对象。例如，考虑一个使用cons而不是+的类似过程。

(let ([double-cons (lambda (x) (cons x x))])(double-cons 'a)) ==> (a . a)

注意到double和double cons之间的相似之处，当您得知它们(double和double cons)可以通过添加额外的参数而分解为单个过程(double-any)时，您不应该感到惊讶。

(let ([double-any (lambda (f x) (f x x))])(list (double-any + 13)(double-any cons 'a))) ==> (26 (a . a))

这表明过程可以接受多个实参，并且传递给过程的实参本身也可以是过程。

与let表达式一样，当lambda表达式嵌套在其他lambda或let表达式中时，它们会变得更有趣。

(let ([x 'a])(let ([f (lambda (y) (list x y))])(f 'b))) ==> (a b)

出现在lambda表达式中的x引用的是外部的let表达式绑定的x变量值。变量x在lambda表达式中是自由出现(occur free)的，或者称为lambda表达式的自由变量(free variable)。变量y在lambda表达式中不是自由出现的，因为它被lambda表达式绑定了。在lambda表达式中自由出现的变量应该被绑定，例如，该变量被一个封闭的lambda或let表达式绑定，除非变量(像基本过程的名称)绑定在表达式之外(Onceday注:即外部变量)，如我们在下一节所讨论的那样。

当过程应用于绑定作用域(scope of the bindings)之外的某个地方时，对于在过程中自由出现的变量，如下面的表达式所示, 会发生什么情况?

(let ([f (let ([x 'sam])(lambda (y z) (list x y z)))])(f 'i 'am)) ==> (sam i am)

答案是，在创建过程时的绑定(变量)在应用过程时再次生效。即使在应用过程的地方有x的另一个绑定值，这也是正确的(Onceday注:应用过程时仍然采用创建过程时的绑定变量)。

(let ([f (let ([x 'sam])(lambda (y z) (list x y z)))])(let ([x 'not-sam])(f 'i 'am))) ==> (sam i am)

在这两种情况下，x在名为f的过程中的值都是sam。

顺便说一下，let表达式不过是lambda表达式对一组参数表达式(argument expressions)的直接应用。例如，下面的两个表达式是等价的。

(let ([x 'a]) (cons x x)) ≡ ((lambda (x) (cons x x)) 'a)

实际上，let表达式是基于lambda和过程应用之上定义的语法扩展，两者都是核心语法形式。一般来说，下面的任何形式的表达式

(let ((var expr) ...) body1 body2 ...)

都等效于下面的形式：

((lambda (var ...) body1 body2 ...) expr ...)

可以通过3.1节来获取有关核心语法形式和语法扩展的更多信息。

如上所述，lambda的一般形式比我们前面看到的形式要复杂一些，因为正式的参数规格(formal parameter specification)(var ...)不需要是一个规则列表，甚至根本不需要是一个列表。正式的参数规格可以有以下三种形式:

1. 多个变量组成的规则列表(var_1 ... var_n)，例如上面已经看到的这些。
2. 单个变量var_r
3. 多个变量组成的非规则列表(var_1 ... var_n . var_r)

在第一种情况下，必须提供确切的n个实际参数，并且每个变量都绑定到相应的实际参数。

在第二种情况下，任何数量的实际参数都是有效的，所有的实际参数都被放到一个列表中，而这个列表被绑定到单个变量var_r上。

第三种情况是前两种情况的混合(hybrid)。必须提供至少n个实际参数。变量var_1 ... var_n被绑定到相应的实际参数上，变量var_r被绑定到一个包含剩余实际参数的列表上。

在第二种和第三种情况下，var_r有时被称为“rest”形参，因为它保存了那些单独命名的形参之外的其他实际形参。

让我们考虑几个示例，以帮助阐明lambda表达式的更通用语法。

(let ([f (lambda x x)])(f 1 2 3 4)) ==> (1 2 3 4)(let ([f (lambda x x)])(f)) ==> ()(let ([g (lambda (x . y) (list x y))])(g 1 2 3 4)) ==> (1 (2 3 4))(let ([h (lambda (x y . z) (list x y z))])(h 'a 'b 'c 'd)) ==> (a b (c d))

在前两个例子中，名为f的过程接受任意数量的参数。这些参数自动形成一个列表，变量x绑定到该列表上。f的值是这个列表。在第一个例子中，参数是1、2、3和4，所以答案是(1 2 3 4)。在第二个例子中，没有参数，所以答案是空列表()。第三个例子中名为g的过程的值是一个列表，列表的第一个元素是第一个参数，列表的第二个元素是包含其余参数的列表。名字为h的过程类似于g，但分离了第二个参数。当f接受任意数量的参数时，g必须至少接收一个参数，h必须至少接收两个参数。

练习题 2.5.1

Determine the values of the expressions below.

求出下面表达式的值。

a.	(let ([f (lambda (x) x)])(f 'a))b.	(let ([f (lambda x x)])(f 'a))c.	(let ([f (lambda (x . y) x)])(f 'a))d.	(let ([f (lambda (x . y) y)])(f 'a))

练习题 2.5.2

How might the primitive procedure list be defined?

如何定义原始过程列表?

练习题 2.5.3

List the variables that occur free in each of the lambda expressions below. Do not omit variables that name primitive procedures such as + or cons.

列出下面每个lambda表达式中自由出现的变量。不要省略命名原始过程(primitive procedures)的变量，如+或cons。

a.	(lambda (f x) (f x))b.	(lambda (x) (+ x x))c.	(lambda (x y) (f x y))d.	(lambda (x)(cons x (f x y)))e.	(lambda (x)(let ([z (cons x y)])(x y z)))f.	(lambda (x)(let ([y (cons x y)])(x y z)))

2.6 顶层定义(Top-Level Definitions)

let和lambda表达式绑定的变量在这些表达式之外是不可见的。假设您创建了一个对象，也许是一个过程，它必须可以在任何地方访问，比如像+或cons一样。您需要的是一个顶层定义，可以使用define来建立它。大多数交互Scheme系统支持的顶层定义在您输入的每个表达式中都是可见的，但被另一个绑定(变量)屏蔽的区域除外。

让我们建立上一节中double-any过程的顶层定义。

(define double-any(lambda (f x)(f x x)))

变量double-any现在具有与cons或任何其他原始过程的名称相同的状态。我们可以像使用原始过程一样使用double-any。

(double-any + 10) ==> 20
(double-any cons 'a) ==> (a . a)

可以为任何对象建立顶层定义，而不仅仅是过程。

(define sandwich "peanut-butter-and-jelly")
sandwich ==> "peanut-butter-and-jelly"

不过，最常见的情况是，顶层定义用于过程。

如上所述，顶层定义可能会被let或lambda绑定变量屏蔽。

(define xyz '(x y z))
(let ([xyz '(z y x)])xyz) ==> (z y x)

具有顶层定义的变量的行为几乎就像是被绑定在一个包含所有输入表达式的let表达式中一样。

截止到目前为止，用你阅读过的这些简单的工具，已经可以定义Scheme提供的一些原始过程，它们在本书后面被描述。如果您完成了上一节的练习，您应该已经知道如何定义list。

(define list (lambda x x))

Scheme还提供了缩写cadr(cdr+car)和cddr(cdr+cdr)，它们由基本的car和cdr组成。也就是说，(cadr list)等价于(car (cdr list))，同样，(cddr list)等价于(cdr (cdr list))。它们很容易定义如下:

(define cadr(lambda (x)(car (cdr x))))(define cddr(lambda (x)(cdr (cdr x))))(cadr '(a b c)) ==> b
(cddr '(a b c)) ==> (c)

任何expr是lambda表达式，其定义(define var expr)都可以用更短的形式编写，即不使用lambda表达式。确切的语法取决于lambda表达式的形式参数说明符(formal parameter specifier)的格式，即该说明符是一个变量组成的规则列表，还是一个单独的变量，亦或是一个变量组成的非规则列表。如下形式的定义，

(define var0(lambda (var1 ... varn)e1 e2 ...))

可以被缩写为：

(define (var0 var1 ... varn)e1 e2 ...)

对于下面表达式，

(define var0(lambda varre1 e2 ...))

可以被缩写成：

(define (var0 . varr)e1 e2 ...)

而下面这种，

(define var0(lambda (var1 ... varn . varr)e1 e2 ...))

可以被写成下面形式：

(define (var0 var1 ... varn . varr)e1 e2 ...)

例如，cadr和list的定义可以写成如下形式。

(define (cadr x)(car (cdr x)))(define (list . x) x)

本书不经常使用这种替代语法。尽管它较短，但它往往掩盖了一个事实，即过程不像在许多其他语言中那样与变量或名称紧密相连。这种语法通常被称为define的“defun”语法(有些贬义)。在Lisp语言提供defun形式之后，过程与它们的名称联系更紧密了。

顶层定义使我们更容易以交互的方式测试过程，因为我们不需要每次使用过程时都重新键入它。让我们试着定义一个稍微复杂一点的double-any变体，它将一个“普通的”双参数过程变成一个“双”单参数过程。

(define doubler(lambda (f)(lambda (x) (f x x))))

Doubler接受一个参数f，它必须是一个接受两个参数的过程。doubler返回的过程接受一个实参，其用于f的调用过程中的两个实参。我们可以使用doubler定义上一节的简单double和double-cons过程。

(define double (doubler +))
(double 13/2) ==> 13(define double-cons (doubler cons))
(double-cons 'a) ==> (a . a)

也可以使用doubler定义double-any:

(define double-any(lambda (f x)((doubler f) x)))

在double和double cons范围内，f具有适当的值，即+或cons，即使过程明显应用于f的定义范围之外。

如果您试图使用一个变量，且它不受let或lambda表达式绑定和非顶层定义，会发生什么情况? 尝试使用变量i-am-not-defined来查看发生了什么。

(i-am-not-defined 3)

大多数Scheme系统打印一条消息，指示发生了未绑定或未定义的变量异常。

但是，系统不应该抱怨lambda表达式中出现了未定义的变量，除非应用了最终过程(resulting procedure)。即使我们还没有建立proc2的顶层定义，下面的操作也不应该导致异常。

(define proc1(lambda (x y)(proc2 y x)))

如果在定义proc2之前尝试应用proc1，则应该得到未定义的异常消息。让我们给proc2一个顶层定义并尝试proc1。

(define proc2 cons)
(proc1 'a 'b) ==> (b . a)

当您定义proc1时，系统接受您定义proc2的承诺，并且不会抱怨，除非您在定义proc2之前使用proc1。这允许您以任意顺序定义过程。当您试图以一种使程序更具可读性的方式组织一个满是过程定义的文件时，这尤其有用。当在顶层定义的两个过程相互依赖时，这是必要的，稍后我们将看到一些这样的例子。

练习题 2.6.1

What would happen if you were to type

(double-any double-any double-any)

given the definition of double-any from the beginning of this section?

对于本节一开始给出的double-any定义，如果你输入上面这个表达式，将会发生什么？

(Onceday注：Ctrl + C可以强制退出交互式Shell)

练习题 2.6.2

A more elegant (though possibly less efficient) way to define cadr and cddr than given in this section is to define a procedure that composes two procedures to create a third. Write the procedure compose, such that (compose p1 p2) is the composition of p1 and p2 (assuming both take one argument). That is, (compose p1 p2) should return a new procedure of one argument that applies p1 to the result of applying p2 to the argument. Use compose to define cadr and cddr.

有一种比本节给出的更优雅(尽管可能效率较低)的方法来定义cadr和cddr，即定义一个由两个过程组成的过程来创建第三个过程。编写过程compose，使(compose p1 p2)是p1和p2的复合过程(假设两者都采用一个参数)。也就是说，(compose p1 p2)应该返回一个包含一个参数的新过程，该过程将p1应用于p2过程的结果，该结果来自于p2应用于给定的参数。使用compose定义cadr和cddr。

练习题 2.6.3

Scheme also provides caar, cdar, caaar, caadr, and so on, with any combination of up to four a’s (representing car) and d’s (representing cdr) between the c and the r (see Section 6.3). Define each of these with the compose procedure of the preceding exercise.

Scheme还提供了car、cdar、caaar、caadr等，在c和r之间使用最多四个a(表示car)和d(表示cdr)的任意组合(参见6.3节)。用前面练习中的compose过程来定义它们。

2.7 条件表达式(Conditional Expressions)

到目前为止，我们已经考虑了无条件执行给定任务的表达式。假设我们希望编写一个过程abs。如果它的参数x是负数，abs返回-x。写abs最直接的方法是确定参数是否为负数，如果是, 则取它的负数，可使用if语法形式来实现。

(define abs(lambda (n)(if (< n 0)(- 0 n)n)))(abs 77) ==> 77
(abs -77) ==> 77

if表达式具有这样的形式(if test consequent alternative)，其中，consequent是求值test为真时执行的表达式，而alternative是求值test为假时执行的表达式。在上面的表达式中，test是(< n 0)，consequent为(- 0 n)，alternative为n。

程序abs可以用各种其他方式编写。以下是abs的有效定义。

(define abs(lambda (n)(if (>= n 0)n(- 0 n))))(define abs(lambda (n)(if (not (< n 0))n(- 0 n))))(define abs(lambda (n)(if (or (> n 0) (= n 0))n(- 0 n))))(define abs(lambda (n)(if (= n 0)0(if (< n 0)(- 0 n)n))))(define abs(lambda (n)((if (>= n 0) + -)0n)))

第一个定义问n是否大于等于零，这与(之前的)测试相反。第二个问n是否不小于零，使用过程not和<。第三个问题问n是大于零还是n等于零，使用语法形式or。第四种方法将0单独处理，尽管这样做没有任何好处。第五个问题有点棘手，n是与0相加还是从0减去(其本身)，取决于n是大于还是等于0。

为什么if是一种语法形式而不是过程? 为了回答这个问题，让我们回顾一下本章第一节中倒数(reciprocal)的定义。

(define reciprocal(lambda (n)(if (= n 0)"oops!"(/ 1 n))))

除法过程的第二个参数不应该是零，因为结果在数学上没有定义。我们对倒数的定义通过在除法之前检验是否为零来避免这个问题。如果是一个过程，它的参数(包括(/ 1 n))将在“结果”(consequent)和“备选”(alternative)之间做出选择之前就被求值。就像quote，它不计算它唯一的子表达式，if也不计算它的所有子表达式，因此不能成为一个过程。

语法形式or的运作方式类似于if。or表达式的一般形式是(or expr ...)。如果没有子表达式，即表达式是简单的(or)，则值为false。否则，每个expr将依次求值，直到(a)其中一个表达式求值为true或(b)没有更多表达式。如果(a)，值为true;如果(b)，则值为false。

更准确地说，在(a)情况下，or表达式的值是最后一个子表达式的值。这种澄清是必要的，因为有许多可能的真值。通常，测试表达式的值是两个对象之一:#t(表示true)或#f(表示false)。

(< -1 0) ==> #t
(> -1 0) ==> #f

不管如何，通过条件表达式和过程not，每个Scheme对象要么是true或者是false。只有#f被认为是false，所有其他对象都被认为是true。

(if #t 'true 'false) ==> true
(if #f 'true 'false) ==> false
(if '() 'true 'false) ==> true
(if 1 'true 'false) ==> true
(if '(a b c) 'true 'false) ==> true(not #t) ==> #f
(not "false") ==> #f
(not #f) ==> #t(or) ==> #f
(or #f) ==> #f
(or #f #t) ==> #t
(or #f 'a #f) ==> a

and语法形式在形式上类似于or，不过and表达式只在所有子表达式都为真时才为真，否则为假。在没有子表达式的情况下，即表达式是简单的(and)，则值为true。否则，依次计算子表达式，直到没有更多的子表达式或子表达式的值为false为止。and表达式的值是最后一个子表达式的值。

使用and，我们可以定义与之前有些许不同的倒数版本。

(define reciprocal(lambda (n)(and (not (= n 0))(/ 1 n))))(reciprocal 3) ==> 1/3
(reciprocal 0.5) ==> 2.0
(reciprocal 0) ==> #f

在这个版本中，如果n为零，则值为#f，否则为1/n。

过程=、<、>、<=和>=称为谓词(predicate)。谓词(predicate)是一个过程，它回答关于其参数的特定问题，并返回两个值中的一个#t或#f。大多数谓词的名称以问号(?)结尾。但是上面列出的常见数值过程(common numeric procedures)是此规则的例外。当然，并非所有谓词都需要数值参数。谓词null?如果参数为空list()则返回true，否则返回false。

(null? '()) ==> #t
(null? 'abc) ==> #f
(null? '(x y z)) ==> #f
(null? (cdddr '(x y z))) ==> #t

过程cdr只能被传递一个序对作为参数，如果不是将引发异常。然而，Common Lisp将(cdr '())定义为()。下面的过程lisp-cdr使用null?返回()，此时list-cdr的参数是()。

(define lisp-cdr(lambda (x)(if (null? x)'()(cdr x))))(lisp-cdr '(a b c)) ==> (b c)
(lisp-cdr '(c)) ==> ()
(lisp-cdr '()) ==> ()

另一个有用的谓词是eqv?，它需要两个参数。如果两个参数相等，则eqv?返回true。否则，eqv?返回false。

(eqv? 'a 'a) ==> #t
(eqv? 'a 'b) ==> #f
(eqv? #f #f) ==> #t
(eqv? #t #t) ==> #t
(eqv? #f #t) ==> #f
(eqv? 3 3) ==> #t
(eqv? 3 2) ==> #f
(let ([x "Hi Mom!"])(eqv? x x)) ==> #t
(let ([x (cons 'a 'b)])(eqv? x x)) ==> #t
(eqv? (cons 'a 'b) (cons 'a 'b)) ==> #f

如你所见，对于eqv?，如果参数是相同的符号、布尔值、数字、序对或字符串，则返回true。如果两个序对是由cons的不同调用创建的，即使它们具有相同的内容，那么它们依然会被eqv?认为不相等。eqv?的详细求值规则记载于第6.2节。

Scheme还提供了一组类型谓词(type predicates)，根据对象的类型返回true或false，例如pair?，symbol?，number?和string?。例如谓词pair?，只有当它的参数是一个序对(pair)时，才返回true。

(pair? '(a . c)) ==> #t
(pair? '(a b c)) ==> #t
(pair? '()) ==> #f
(pair? 'abc) ==> #f
(pair? "Hi Mom!") ==> #f
(pair? 1234567890) ==> #f

类型谓词用于判断传递给过程的参数是否属于适当的类型。例如，下面的倒数(reciprocal)版本首先检查参数是否为数字，然后再测试是否为零或执行除法。

(define reciprocal(lambda (n)(if (and (number? n) (not (= n 0)))(/ 1 n)"oops!")))(reciprocal 2/3) ==> 3/2
(reciprocal 'a) ==> "oops!"

顺便说一下，使用倒数(reciprocal)的代码必须检查返回值是否为数字而不是字符串。为了解除调用方的这一义务，通常最好使用断言违反(assert - violate)来报告错误，如下所示。

(define reciprocal(lambda (n)(if (and (number? n) (not (= n 0)))(/ 1 n)(assertion-violation 'reciprocal"improper argument"n))))(reciprocal .25) ==> 4.0
(reciprocal 0) ==> exception in reciprocal: improper argument 0
(reciprocal 'a) ==> exception in reciprocal: improper argument a

断言违反的第一个参数是标识消息来源的符号，第二个参数是描述错误的字符串，第三个和后面的参数是要包含在错误消息中的“刺激物”。

让我们再看一个条件表达式cond，它通常用来代替if。cond与if类似，不同之处是它允许多个测试test和可选alternative表达式。考虑下面的符号sign定义，它对于负输入返回-1，对于正输入返回+1，对于零返回0。

(define sign(lambda (n)(if (< n 0)-1(if (> n 0)+10))))(sign -88.3) ==> -1
(sign 0) ==> 0
(sign 333333333333) ==> 1
(* (sign -88.3) (abs -88.3)) ==> -88.3

两个if表达式可以替换为一个cond表达式，如下所示:

(define sign(lambda (n)(cond[(< n 0) -1][(> n 0) +1][else 0])))

一个cond表达式通常具有以下形式：

(cond (test expr) ... (else expr))

尽管else子句可以省略。不过只有在所有测试test都不可能失败的情况下，才应该这样做，就像下面的符号sign的新版本一样。

(define sign(lambda (n)(cond[(< n 0) -1][(> n 0) +1][(= n 0) 0])))

符号sign的这些(test)定义的顺序并不依赖于执行test的顺序，因为对于n的任何值，只有一个测试test是正确的。下面的过程计算在分割点为10,000、20,000和30,000美元的累进税制中给定收入数额的税收。

(define income-tax(lambda (income)(cond[(<= income 10000) (* income .05)][(<= income 20000) (+ (* (- income 10000) .08) 500.00)][(<= income 30000) (+ (* (- income 20000) .13) 1300.00)][else (+ (* (- income 30000) .21) 2600.00)])))(income-tax 5000) ==> 250.0
(income-tax 15000) ==> 900.0
(income-tax 25000) ==> 1950.0
(income-tax 50000) ==> 6800.0

在本例中，执行测试的顺序(从左到右(从上到下)非常重要。

练习题 2.7.1

Define the predicate atom?, which returns true if its argument is not a pair and false if it is.

定义谓词atom?，如果参数不是一个序对则返回true，如果是一个序对则返回false。

练习题 2.7.2

The procedure length returns the length of its argument, which must be a list. For example, (length '(a b c)) is 3. Using length, define the procedure shorter, which returns the shorter of two list arguments. Have it return the first list if they have the same length.

过程length返回其参数的长度，必须是一个列表list。例如，(length '(a b c))是3。使用length定义更短的过程，它返回两个列表参数中较短的那个。如果长度相同，让它返回第一个列表。

(shorter '(a b) '(c d e)) ==> (a b)
(shorter '(a b) '(c d)) ==> (a b)
(shorter '(a b) '(c)) ==> (c)

2.8 简单递归(Simple Recursion)

我们已经了解了如何使用if、and、or和cond对“是否”表达式(whether or not expressions)求值。还可以多次执行一个表达式，方法是创建包含该表达式的过程并多次调用该过程。如果我们需要重复执行某个表达式，比如针对列表的所有元素或从1到10的所有数字，该怎么办? 我们可以通过递归来实现。递归是一个简单的概念:从过程中应用一个过程。刚开始掌握递归可能很棘手，但一旦掌握了它，它提供的表达能力远远超过普通循环结构。

递归过程是应用于自身的过程。也许最简单的递归过程是下面这个，我们将称之为再见goodbye。

(define goodbye(lambda ()(goodbye)))(goodbye) ==>

这个过程没有参数，只是简单地立即应用自己。在==>之后没有值。因为再见goodbye一去不复返。

显然，要实际利用递归过程，必须有终止递归的方法。大多数递归过程应该至少有两个基本元素，一个基本条件和一个递归步骤。基本条件终止递归，给出某个基本参数的过程值。递归步骤根据“应用于不同实参的过程”的值从而给出最终值。为了结束递归，不同的实参必须以某种方式更接近于基本实参。

让我们考虑一下递归地寻找规则列表的长度的问题。我们需要一个基本条件和一个递归步骤。列表上递归的基本逻辑参数几乎总是空列表。空列表的长度为零，因此基本情况应该为空列表提供零值。为了更接近空列表，自然递归步骤涉及参数的cdr过程。非空列表比它的cdr多一个元素，因此递归步骤给出的值比列表的cdr长度多一个。

(define length(lambda (ls)(if (null? ls)0(+ (length (cdr ls)) 1))))(length '()) ==> 0
(length '(a)) ==> 1
(length '(a b)) ==> 2

if表达式询问列表是否为空。如果是，则值为零。这是基本条件。如果不是，则该值比列表的cdr长度大1。这是递归步骤。

许多Scheme实现允许您跟踪过程的执行，以查看它是如何操作的。例如，在Chez Scheme中，跟踪过程的一种方法是键入(trace name)，其中name是您在顶层定义的过程的名称。如果你跟踪上面定义的length并传递参数'(a b c d)，你应该看到如下内容:

|(length (a b c d))
| (length (b c d))
| |(length (c d))
| | (length (d))
| | |(length ())
| | |0
| | 1
| |2
| 3
|4

缩进表示递归的嵌套级别，竖线将应用程序与它们的值在视觉上关联起来。注意，在每个长度相同的应用程序中，列表会越来越小，直到最终达到()。空列表()的长度值为0，每个外层过程加1得到最终值。

让我们写一个过程，list-copy，它返回参数的副本，该参数必须是一个列表。也就是说，list-copy返回一个由旧列表的元素(而不是序对)组成的新列表。如果原始列表或副本可能通过set-car!或set-cdr !更改，那么制作一个副本可能是有用的! 这个问题我们稍后再讨论。

(list-copy '()) ==> ()
(list-copy '(a b c)) ==> (a b c)

在学习下面的定义之前，看看你能否定义list-copy。

(define list-copy(lambda (ls)(if (null? ls)'()(cons (car ls)(list-copy (cdr ls))))))

list-copy的定义类似于length的定义。基本条件中的测试是相同的(null? ls)。但是，基本条件中的值是()，而不是0，因为我们正在构建一个列表，而不是一个数字。递归调用是相同的，但不是加一，list-copy将列表中的car与递归调用的返回值用cons组成一个序对。

没有理由说不能有多个基本条件。过程memv接受两个参数，一个对象和一个列表。如果列表的car值等于对象，那么返回该列表第一个子列表或尾部，如果在列表中没有找到该对象，则返回#f。memv的值可以用作列表，也可以用作条件表达式中的真值(truth value)。

(define memv(lambda (x ls)(cond[(null? ls) #f][(eqv? (car ls) x) ls][else (memv x (cdr ls))])))(memv 'a '(a b b d)) ==> (a b b d)
(memv 'b '(a b b d)) ==> (b b d)
(memv 'c '(a b b d)) ==> #f
(memv 'd '(a b b d)) ==> (d)
(if (memv 'b '(a b b d))"yes""no") ==> "yes"

这里有两个条件需要检查，因此使用cond。第一个cond子句检查()的基本值(base value)，没有对象是()的成员，所以答案是#f。第二个子句询问列表中的car是否就是目标对象，在这种情况下，返回列表，即第一个其car包含目的对象的尾部(tail)。递归步骤只是沿着列表继续。

也可能存在不止一种递归情况。与memv一样，下面定义的过程remv也接受两个参数，一个对象和一个列表。它返回一个新列表，其中包含从列表中删除的所有目的对象。

(define remv(lambda (x ls)(cond[(null? ls) '()][(eqv? (car ls) x) (remv x (cdr ls))][else (cons (car ls) (remv x (cdr ls)))])))(remv 'a '(a b b d)) ==> (b b d)
(remv 'b '(a b b d)) ==> (a d)
(remv 'c '(a b b d)) ==> (a b b d)
(remv 'd '(a b b d)) ==> (a b b)

这个定义类似于上面memv的定义，除了remv在找到列表的car中的元素后不会退出之外。相反，它继续遍历，简单地忽略元素。如果在列表的car中没有找到元素，则remv执行与上面的list-copy相同的操作：将列表中的car与递归调用的返回值用cons组成一个序对。

到目前为止，递归只在列表的cdr上进行。然而，它有时对于列表的car上重复执行一个过程也是有用的，如同在cdr上遍历一样。下面定义的过程tree-copy将序对的结构视为树而不是列表，左边的子树是序对的car，右边的子树是序对的cdr。它执行与list-copy类似的操作，在保持元素不变的情况下构建新的序对。

(define tree-copy(lambda (tr)(if (not (pair? tr))tr(cons (tree-copy (car tr))(tree-copy (cdr tr))))))(tree-copy '((a . b) . c)) ==> ((a . b) . c)

树结构的自然基本参数(natural base argument，Onceday注:意指基本判断条件(not (pair? tr))的参数)是任何不是序对的东西，因为递归是在遍历序对而不是列表。本例中的递归步骤是双重递归的，以递归的方式查找传入参数的car值以及cdr值。

在这一点上，读者如果熟悉提供特殊迭代构造(例如while或for循环)的其他语言，可能想知道Scheme中是否需要类似的构造。这样的构造是不必要的，因为Scheme中的迭代通过递归实现，其更清晰、简洁。递归更加通用，并且消除了许多其他语言的迭代构造所需要的变量赋值，从而产生了更可靠、更容易理解的代码。有些递归本质上是迭代，并且这样(迭代)执行。第3.2节对此有更多的说明。然而，通常没有必要做出区分，因为(程序员)应该专注于编写清晰、简洁和正确的程序。

在结束递归主题之前，让我们考虑一种称为映射(mapping)的特殊重复形式。考虑下面的过程abs-all，它接受一个数字列表作为输入，并返回它们的绝对值列表。

(define abs-all(lambda (ls)(if (null? ls)'()(cons (abs (car ls))(abs-all (cdr ls))))))(abs-all '(1 -2 3 -4 5 -6)) ==> (1 2 3 4 5 6)

这个过程通过对每个元素应用abs过程，从输入列表形成一个新列表。我们说abs-all在输入列表上映射abs以生成输出列表。将过程映射到列表是一件相当常见的事情，因此Scheme提供了过程映射(procedure map)，它将其第一个参数(过程)映射到第二个参数(列表)。我们可以使用map来定义abs-all。

(define abs-all(lambda (ls)(map abs ls)))

但是，我们真的不需要abs-all，因为相应的直接应用map过程同样简短，而且可能更清楚。

(map abs '(1 -2 3 -4 5 -6)) ==> (1 2 3 4 5 6)

当然，我们可以使用lambda来创建要映射map的过程参数(procedure argument)，例如，对数字列表的每个元素进行平方。

(map (lambda (x) (* x x))'(1 -3 -5 7)) ==> (1 9 25 49)

我们可以在多个列表上映射一个多参数过程，如下面的示例所示:

(map cons '(a b c) '(1 2 3)) ==> ((a . 1) (b . 2) (c . 3))

列表的长度必须相同，并且过程接受的参数数量和列表的数量一致。输出列表的每个元素都是将该过程应用到输入列表的对应成员的结果。

查看上面abs-all的第一个定义，在学习它之前，您应该能够推导出map1的以下定义，这是map的受限版本，它将一个参数过程映射到单个列表上。

(define map1(lambda (p ls)(if (null? ls)'()(cons (p (car ls))(map1 p (cdr ls))))))(map1 abs '(1 -2 3 -4 5 -6)) ==> (1 2 3 4 5 6)

我们所做的只是将abs-all中的对abs的调用替换为对新形参p的调用。更通用的映射的定义在第5.4节给出。

练习题 2.8.1

Describe what would happen if you switched the order of the arguments to cons in the definition of tree-copy.

描述一下如果将树复制定义中的实参顺序切换为反序会发生什么。

练习题 2.8.2

Consult Section 6.3 for the description of append and define a two-argument version of it. What would happen if you switched the order of the arguments in the call to append within your definition of append?

关于append的描述请参阅第6.3节，并定义它的双参数版本。如果在你的append定义中交换参数(其调用了append)的顺序，会发生什么情况?

练习题 2.8.3

Define the procedure make-list, which takes a nonnegative integer n and an object and returns a new list, n long, each element of which is the object.

定义make-list过程，它接受一个非负整数n和一个对象，并返回一个长为n的新列表，其中的每个元素都是对象。

(make-list 7 '()) ==> (() () () () () () ())

[Hint: The base test should be (= n 0), and the recursion step should involve (- n 1). Whereas () is the natural base case for recursion on lists, 0 is the natural base case for recursion on nonnegative integers. Similarly, subtracting 1 is the natural way to bring a nonnegative integer closer to 0.]

[提示:基本测试条件应该是(= n 0)，递归步骤应该涉及(- n 1)。()是在列表上递归的自然基本条件，0是在非负整数上递归的自然基本条件。类似地，减去1是使非负整数更接近0的自然方法。]

练习题 2.8.4

The procedures list-ref and list-tail return the nth element and nth tail of a list ls.

过程list-ref和list-tail返回列表ls的第n个元素和第n个尾部。

(list-ref '(1 2 3 4) 0) ==> 1
(list-tail '(1 2 3 4) 0) ==> (1 2 3 4)
(list-ref '(a short (nested) list) 2) ==> (nested)
(list-tail '(a short (nested) list) 2) ==> ((nested) list)

Define both procedures.

定义这两个过程。

练习题 2.8.5

Exercise 2.7.2 had you use length in the definition of shorter, which returns the shorter of its two list arguments, or the first if the two have the same length. Write shorter without using length. [Hint: Define a recursive helper, shorter?, and use it in place of the length comparison.]

练习2.7.2让您在shorter的定义中使用了length，它返回两个列表参数中较短的一个，如果两个参数的长度相同则返回第一个。实现shorter，但不要使用length过程。[提示:定义一个递归协助过程，shorter?，并使用它来代替长度比较。]

练习题 2.8.6

All of the recursive procedures shown so far have been directly recursive. That is, each procedure directly applies itself to a new argument. It is also possible to write two procedures that use each other, resulting in indirect recursion. Define the procedures odd? and even?, each in terms of the other. [Hint: What should each return when its argument is 0?]

目前所展示的所有递归过程都是直接递归的。也就是说，每个过程都直接应用于一个新的实参。也可以编写两个相互使用的过程，从而产生间接递归。定义过程odd?和even?，彼此之间相互依赖。[提示:当参数为0时，每个过程应该返回什么?]

(even? 17) ==> #f
(odd? 17) ==> #t

练习题 2.8.7

Use map to define a procedure, transpose, that takes a list of pairs and returns a pair of lists as follows.

使用map定义转置transpose过程，它接受一个由序对组成的列表，并返回一个由列表组成的序对，如下所示。

(transpose '((a . 1) (b . 2) (c . 3))) ==> ((a b c) 1 2 3)

[Hint: ((a b c) 1 2 3) is the same as ((a b c) . (1 2 3)).]

提示：上面这两个表达式是等效的。

2.9 赋值过程

尽管许多程序可以在没有它们的情况下编写，但对顶层变量或let-bound和lambda-bound变量的赋值有时是有用的。赋值不会像let或lambda那样创建新的绑定(变量)，而是更改现有绑定(变量)的值。赋值使用set!

(define abcde '(a b c d e))
abcde ==> (a b c d e)
(set! abcde (cdr abcde))
abcde ==> (b c d e)
(let ([abcde '(a b c d e)])(set! abcde (reverse abcde))abcde) ==> (e d c b a)

许多语言需要使用赋值来初始化局部变量，即变量的声明或绑定是分开的。在Scheme中，所有局部变量在绑定时立即被赋予一个值。除了使初始化局部变量的单独赋值变得不必要之外，它还确保程序员不会忘记初始化它们，这是大多数语言中常见的错误来源。

事实上，大多数在其他语言中必要或方便的赋值在Scheme中都是不必要和不方便的，因为通常有更清晰的方式来表达相同的算法而不需要赋值。在某些语言中，一种常见的做法是用一系列赋值对一组连续表达式求值，如下面的过程，其计算二次方程的根。

(define quadratic-formula(lambda (a b c)(let ([root1 0] [root2 0] [minusb 0] [radical 0] [divisor 0])(set! minusb (- 0 b))(set! radical (sqrt (- (* b b) (* 4 (* a c)))))(set! divisor (* 2 a))(set! root1 (/ (+ minusb radical) divisor))(set! root2 (/ (- minusb radical) divisor))(cons root1 root2))))

二次方程的根是根据著名的二次公式计算的：
− b ± b 2 − 4 a c 2 a \frac{-b\pm \sqrt{b^2 - 4ac}}{2a} 2a−b±b2−4ac ​​
这个公式得出了方程 0 = a x 2 + b x + c 0=ax^2+bx+c 0=ax2+bx+c的解，在这个过程定义中的let表达式仅被用于建立绑定变量(the variable binding)，正如在其他语言中所要求的的变量声明一样。首先，三个赋值表达式分别计算了该公式的子项，也就是-b， b 2 − 4 a c \sqrt{b^2-4ac} b2−4ac ​和2a。最后的两个赋值表达式在这些子项的值上计算两个根。由两个根组成的序对就是二次方程的解值。例如，方程 2 x 2 − 4 x − 6 2x^2-4x-6 2x2−4x−6的根是$x=3$和$x=-1$。

(quadratic-formula 2 -4 -6) ==> (3 . -1)

上面的定义是有效的，但是，不用赋值可以写出更简洁的形式，如下所示。

(define quadratic-formula(lambda (a b c)(let ([minusb (- 0 b)][radical (sqrt (- (* b b) (* 4 (* a c))))][divisor (* 2 a)])(let ([root1 (/ (+ minusb radical) divisor)][root2 (/ (- minusb radical) divisor)])(cons root1 root2)))))

在这个版本里面，丢掉了set!表达式，剩下的是本质上相同的算法过程。然而，通过采用两个let表达式，这个过程定义清楚的说明了root1和root2对minusb，radical和divisor值的依赖性。同样重要的是，let表达式明确了minusb、radical和divisor之间以及root1和root2之间缺乏依赖关系。

赋值在Scheme中确实有一些用途，不然语言就不会支持它们了。考虑下面的cons版本，它计算调用次数，并将计数存储在名为cons-count的变量中。它使用set!增加计数。没有办法不使用赋值语句来达到同样的行为。

(define kons-count 0)
(define kons(lambda (x y)(set! kons-count (+ kons-count 1))(cons x y)))(kons 'a '(b c)) ==> (a b c)
kons-count ==> 1
(kons 'a (kons 'b (kons 'c '()))) ==> (a b c)
kons-count ==> 4

赋值通常用于实现必须维护某些内部状态的过程。例如，假设我们想定义一个过程，它在第一次被调用时返回0，第二次返回1，第三次返回2，以此类推。我们可以写一些类似于上面con -count定义的东西:

(define next 0)
(define count(lambda ()(let ([v next])(set! next (+ next 1))v)))(count) ==> 0
(count) ==> 1

这个解决方案在某种程度上是不受欢迎的，因为变量next在顶层是可见的，然而它不并需要可见。正是因为它在顶层可见，所以系统中的任何代码都可以更改它的值，这可能会以一种微妙的方式无意中影响count的行为。我们可以通过在lambda表达式外面的(let 绑定变量)let-binding next来解决这个问题:

(define count(let ([next 0])(lambda ()(let ([v next])(set! next (+ next 1))v))))

后一种解决方案也很容易推广，可以提供多个计数器，每个计数器都有自己的本地计数器。下面定义的过程make-counter每次被调用时都会返回一个新的计数过程。

(define make-counter(lambda ()(let ([next 0])(lambda ()(let ([v next])(set! next (+ next 1))v)))))

由于next被绑定在make-counter的内部，同时也绑定在make-counter返回的(计数)过程的外部，所以它返回的每个(计数)过程都维护自己唯一的计数器。

(define count1 (make-counter))
(define count2 (make-counter))(count1) ==> 0
(count2) ==> 0
(count1) ==> 1
(count1) ==> 2
(count2) ==> 1

如果一个状态变量必须由在顶层定义的多个过程共享，但我们不希望状态变量在顶层可见，那么可以使用let绑定该变量并使用sed!使(其他)过程在顶层可见(该变量)。

(define shhh #f)
(define tell #f)
(let ([secret 0])(set! shhh(lambda (message)(set! secret message)))(set! tell(lambda ()secret)))(shhh "sally likes harry")
(tell) ==> "sally likes harry"
secret ==> exception: variable secret is not bound

变量在赋值之前必须定义，因此我们定义shhh和tell，并设置初始值为#f。(任何初始值都可以。)我们将在第3.5节中再次看到这种结构，并在第3.6节中看到将这样的代码构造为库的更好方法。

局部状态有时对于缓存计算或允许延迟计算(evaluated lazily)(即只按需计算一次)非常有用。下面的lazy过程接受一个thunk(即零参数过程)作为参数。thunks通常用于“冻结freeze”由于某种原因必须延迟的计算，这正是我们在这种情况下需要做的。当传递一个thunk t时，lazy返回一个新的thunk，当调用该thunk时，返回调用t的值。一旦计算完成，该值将保存在一个局部变量中，这样计算就不需要再次执行。布尔标志用于记录是否调用了t并保存了它的值。

(define lazy(lambda (t)(let ([val #f] [flag #f])(lambda ()(if (not flag)(begin (set! val (t))(set! flag #t)))val))))

这里第一次使用了语法形式begin，其按从左到右的顺序计算它的子表达式，并返回最后一个子表达式的值，就像let或lambda表达式的主体(一系列的子表达式)一样。我们还看到，可以省略if表达式的备选(alternative)子表达式。只有当if的值被丢弃时，才应该这样做，就像在本例中一样。

惰性求值对于需要大量时间计算的值特别有用。通过延迟计算，我们可以避免计算整个值，通过保存值，我们可以避免计算多次。

lazy的操作可以通过在传递给lazy的trunk过程中打印消息来最好地说明。

(define p(lazy (lambda ()(display "Ouch!")(newline)"got me")))

第一次调用p时，打印消息“Ouch!”并返回字符串"got me"。在这之后，只返回"got me"，但不打印消息。过程display和newline是我们看到显式输入/输出的第一个例子：Display打印不带引号的字符串，newline打印换行符。

进一步说明set!，让我们考虑一下堆栈对象的实现，这些对象的内部工作在外部是不可见的。堆栈对象接受四个消息中的一个：empty?，如果堆栈为空，则返回#t。push!，将一个对象添加到堆栈的顶部。top，它返回堆栈顶部的对象。pop!，它将移除堆栈顶部的对象。下面给出的make-stack过程每次在以类似于make-counter的方式调用时将创建一个新堆栈。

(define make-stack(lambda ()(let ([ls '()])(lambda (msg . args)(cond[(eqv? msg 'empty?) (null? ls)][(eqv? msg 'push!) (set! ls (cons (car args) ls))][(eqv? msg 'top) (car ls)][(eqv? msg 'pop!) (set! ls (cdr ls))][else "oops"])))))

每个堆栈都存储为"绑定变量"ls的列表。set!用于为push!和pop!更改"绑定变量"的值。内部lambda表达式的参数列表使用了非规则列表语法，将args绑定到除第一个参数外的其他所有参数组成的列表上。这在这里很有用，因为在empty?，top，pop!只有一个参数(消息)，但在push!有两个(消息和要压入堆栈的对象)。

(define stack1 (make-stack))
(define stack2 (make-stack))
(list (stack1 'empty?) (stack2 'empty?)) ==> (#t #t)(stack1 'push! 'a)
(list (stack1 'empty?) (stack2 'empty?)) ==> (#f #t)(stack1 'push! 'b)
(stack2 'push! 'c)
(stack1 'top) ==> b
(stack2 'top) ==> c(stack1 'pop!)
(stack1 'top) ==> a
(list (stack1 'empty?) (stack2 'empty?)) ==> (#f #f)(stack1 'pop!)
(list (stack1 'empty?) (stack2 'empty?)) ==> (#t #f)

与make-counter创建的计数器一样，每个堆栈对象维护的状态只能在对象内部直接访问。对该状态的每次引用或更改都是由对象本身显式进行的。一个重要的好处是，我们可以改变堆栈的内部结构，比如使用vector(参见第6.9节)而不是list来保存元素，但是不改变其外部行为。因为对象的行为看起来是抽象地(abstractly)(而不是操作地(operationally))，所以它被称为抽象对象(abstract object)。有关创建抽象对象(abstract object)的更多信息，请参见12.8节。

除了更改变量的值之外，我们还可以使用set-car!和set-cdr!。

(define p (list 1 2 3))
(set-car! (cdr p) 'two)
p ==> (1 two 3)
(set-cdr! p '())
p ==> (1)

我们可以使用这些操作符来定义队列数据类型，它类似于堆栈，只不过在一端添加新元素，并从另一端提取新元素。下面的队列实现使用了tconc结构。tconc由一个非空列表和一个头部组成。头部是一个序对，其car指向列表的第一个序对(头)，cdr指向列表的最后一个序对(尾)。

列表的最后一个元素是占位符，不被视为队列的一部分。

下面定义了队列上的四个操作：

• make-queue，它构造了一个队列。
• putq!，将一个元素添加到队列的末尾。
• getq，检索队列前面的元素。
• delq!，它会删除队列前面的元素。

(define make-queue(lambda ()(let ([end (cons 'ignored '())])(cons end end))))(define putq!(lambda (q v)(let ([end (cons 'ignored '())])(set-car! (cdr q) v)(set-cdr! (cdr q) end)(set-cdr! q end))))(define getq(lambda (q)(car (car q))))(define delq!(lambda (q)(set-car! q (cdr (car q)))))

除了putq!，它修改尾部序对(end pair)以包含新值，并添加一个新的尾部序对(end pair)。

(define myq (make-queue))(putq! myq 'a)
(putq! myq 'b)
(getq myq) ==> a
(delq! myq)
(getq myq) ==> b
(delq! myq)
(putq! myq 'c)
(putq! myq 'd)
(getq myq) ==> c
(delq! myq)
(getq myq) ==> d

练习题 2.9.1

Modify make-counter to take two arguments: an initial value for the counter to use in place of 0 and an amount to increment the counter by each time.

修改make-counter以接受两个参数:一个用于代替0的计数器的初始值，一个用于每次增加计数器的数量。

练习题 2.9.2

Look up the description of case in Section 5.3. Replace the cond expression in make-stack with an equivalent case expression. Add mt? as a second name for the empty? message.

在5.3节中寻找关于case的描述，用等效的case表达式取代make-stack中的cond表达式。新增mt?作为empty?消息的第二个名字。

练习题 2.9.3

Modify the stack object to allow the two messages ref and set!. (stack 'ref i) should return the ith element from the top of the stack; (stack 'ref 0) should be equivalent to (stack 'top). (stack 'set! i v) should change the ith element from the top of the stack to v.

修改stack对象，以允许ref和set!这两个消息。(stack 'ref i)应该从栈的顶部返回第i个元素的值，(stack 'ref 0)应该等效于(stack 'top)。(stack 'set! i v)应该改变从栈顶开始计数的第i个元素的值为v。

(define stack (make-stack))(stack 'push! 'a)
(stack 'push! 'b)
(stack 'push! 'c)(stack 'ref 0) ==> c
(stack 'ref 2) ==> a
(stack 'set! 1 'd)
(stack 'ref 1) ==> d
(stack 'top) ==> c
(stack 'pop!)
(stack 'top) ==> d

[Hint: Use list-ref to implement ref and list-tail with set-car! to implement set!.]

练习题 2.9.4

Scheme supports vectors as well as lists. Like lists, vectors are aggregate objects that contain other objects. Unlike lists, vectors have a fixed size and are laid out in one flat block of memory, typically with a header containing the length of the vector, as in the ten-element vector below.

This makes vectors more suitable for applications needing fast access to any element of the aggregate but less suitable for applications needing data structures that grow and shrink as needed.

Look up the basic vector operations in Section 6.9 and reimplement the stack object to use a vector instead of a list to hold the stack contents. Include the ref and set! messages of Exercise 2.9.3. Have the new make-stack accept a size argument n and make the vector length n, but do not otherwise change the external (abstract) interface.

Scheme支持向量和列表。与列表一样，向量是包含其他对象的聚合对象。与列表不同的是，向量的大小是固定的，并且被布局在一个平坦的内存块中，通常带有包含向量长度的头部，如上面的10元素向量所示。

这使得向量更适合应用于需要快速访问其中的任何元素，但不太适合应用于根据需要来增长或收缩数据结构。

查阅第6.9节中的基本向量操作，并重新实现堆栈对象，使用向量而不是列表来保存堆栈内容。包括练习题2.9.3中的ref和set!消息。让新的make-stack接受size参数n，并使向量长度为n，但不更改外部(抽象)接口。

练习题 2.9.5

Define a predicate, emptyq?, for determining if a queue is empty. Modify getq and delq! to raise an exception when an empty queue is found, using assertion-violation.

定义一个谓词emptyq?，用于确定队列是否为空。修改getq和delq!，使得在找到空队列时引发异常，使用assertion-violation。

练习题 2.9.6

In the queue implementation, the last pair in the encapsulated list is a placeholder, i.e., it never holds anything useful. Recode the queue operators to avoid this wasted pair. Make sure that the series of queue operations given earlier works with the new implementation. Which implementation do you prefer?

在队列实现中，封装的列表中的最后一个序对是占位符，也就是说，它从来没有保存任何有用的东西。对队列操作进行重新编码，以避免这种浪费的序对。确保前面给出的队列操作系列适用于新的(队列)实现。您更喜欢哪种实现?

练习题 2.9.7

Using set-cdr!, it is possible to create cyclic lists. For example, the following expression evaluates to a list whose car is the symbol a and whose cdr is the list itself.

(let ([ls (cons 'a '())])(set-cdr! ls ls)ls)

What happens when you enter the above expression during an interactive Scheme session? What will the implementation of length on page 42 do when given a cyclic list? What does the built-in length primitive do?

使用set-cdr !，则可以创建循环列表。例如，下面的表达式求值为一个列表，它的car是符号a, cdr是列表本身。

在交互Scheme会话中输入上述表达式会发生什么情况? 当给出一个循环列表时，第42页上的length实现会怎么做? 内置的length原型过程又会怎么做?

练习题 2.9.8

Define the predicate list?, which returns #t if its argument is a proper list and #f otherwise (see Section 6.3). It should return #f for cyclic lists as well as for lists terminated by objects other than ().

(list? '()) ==> #t
(list? '(1 2 3)) ==> #t
(list? '(a . b)) ==> #f
(list? (let ([ls (cons 'a '())])(set-cdr! ls ls)ls)) ==> #f

First write a simplified version of list? that does not handle cyclic lists, then extend this to handle cyclic lists correctly. Revise your definition until you are satisfied that it is as clear and concise as possible.

[Hint: Use the following “hare and tortoise” algorithm to detect cycles. Define a recursive help procedure of two arguments, the hare and the tortoise. Start both the hare and the tortoise at the beginning of the list. Have the hare advance by two cdrs each time the tortoise advances by one cdr. If the hare catches the tortoise, there must be a cycle.]

先写一个简化版的list?，它不处理循环列表，然后扩展它以正确处理循环列表。修改你的定义，直到你觉得它尽可能清晰和简洁为止。

[提示:使用下面的“兔子和乌龟”算法来检测循环。定义一个包含两个参数的递归帮助过程，即野兔和乌龟。从列表开头的兔子和乌龟开始。乌龟每前进一个cdr，兔子就前进两个cdr。如果兔子抓住了乌龟，那一定是一个循环。]

(第二章完，真的好多字，道阻且长，后续章节将会慢慢更新…)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！