Scheme语言分析

Wolfgang Kreutzer

翻译：寒蝉退士

原文：http://www.cosc.canterbury.ac.nz/~wolfgang/cosc302/Chap2.3.html

译者声明：译者对译文不做任何担保，译者对译文不拥有任何权利并且不负担任何责任和义务。

APL 如同钻石，有着美妙的晶体结构；它的所有部分都以一致和优美的方式关联在一起。但是如果你尝试以任何方式扩展这种结构 - 即使是增加另一个钻石 - 你将得到一个丑陋的杂种。在另一方面，LISP 如同泥球。你可以向它增加任意数量的泥巴，它看起来还是个泥球。

[J. Moses, as quoted by Steele and Sussman (1978)].

译序：本文是介绍人工智能的一本书的一章，Lisp 的赫赫声名缘于它是人工智能专家们做符号处理的主要编程工具。从计算机技术的角度来说，Lisp 是函数式编程语言的代表，有着“数学基础”领域中 lambda 演算的理论背景。Lisp 的修正版本 Scheme 有着一定的研究价值。

目录：

• 历史演化和关键概念

• 用 Scheme 编程

• 概述

• 表示和解释 - 符号 & 值

• 数据类型和它们的操作

• 导引控制流

• Lambda 表达式和环境

• 执行的嵌套上下文

• 过程 - 定义、测试、调试

• 递归

• 额外特征

• 对风格的一些建议

• 总结和看法

历史演化和关键概念

在人工智能的很多研究中，Lisp 家族语言是最古老的、并仍然是最广泛使用的工具。不象 Fortran 那样，在很大程度上出于经济上的动机而保持语言存活了四分之一个世纪，Lisp 在 AI 社区的兴旺是因为它的某些特征的优越。

Lisp 至关重要的一个方面是试探性程序开发的概念。符号到值的任何提交(commitment)可以延迟直到这样的决定不可避免，即使如此它可以用很小的代价逆转(reverse)。这允许我们快速的探索可供选择的设计并逐步增加的建造程序。Lisp 的语法是简单的、并且它的程序自然的表示为数据结构，所以很容易写操纵其他程序的程序。

还有一些额外的因素被结合了进来，对 Lisp 的持久流行做出了贡献[Hayes (1987)]: 不象 Fortan 或 Cobol，Lisp 持续自由的演化。直到最近 Lisp 程序的经济上的重要性仍是非常低的，这意味着没有任何压力要冻结语言的定义为一个标准的特征集。作为一门 AI 语言，Lisp 长期用来攻击“艰深”问题，这种任务导致了很多新特征和强力工具。Lisp 社区总是接受一种工具建造文化，工具开发者自身典型的也是工具的使用者的事实大力促成了这种事态。Lisp 是非常易于扩展的("增加更多泥巴") 并自愿“让机器去做”。AI 研究总是准备扩展计算机的能力来更好的使用人类资源，这个政策经常导致工具超越了所在时代。被同样的动机所刺激，还有对编程环境和个人工作站的非常早期的兴趣。

这种语言创新的精神已经融入成 Lisp 历史的一部分。这已经由 McCarthy (1978) 和 Stoyan (1980) 详细的写入编年史中。Lisp (List Processing Language) 最初设计为 Fortran 的一个扩展。John McCarthy 那时是 Dartmouth 学院的数学助理教授，他对使用计算机做符号计算(就是说，数学表达式的简化)发生了早期的兴趣, 在“Dartmouth Summer School on Artificial Intelligence”期间受 Newell 和 Simon 对 IPL 介绍的进一步刺激，这个研讨班是 1956 年 McCarthy 和 Shannon 和 Minsky 一起组织的。尽管那时没有任何参与者对如何最终完成人工智能有任何概念，数值计算完全不重要好象是明显的，而操纵符号表达式的能力好象是关键性的。IPL 已经包括了表处理和递归的想法，但它在风味上仍是非常“低级的”。Fortan，刚刚被 IBM 表彰为第一个真正的“高级”编程语言，好象是在正确方向上的前进了一步。不幸的是 Fortran 的设计受满足高效数值计算需要的支配，而导致的僵化使它对于操纵 McCarthy 感兴趣的各种应用需要的高度动态的结构是一个非常薄弱的基矗一个自包含的表处理语言好象是更好的解决方案。此时 McCarthy 也是派到欧洲 Algol(Algorithmic Language)委员会的美洲代表团成员。在这里它提出了条件表达式的概念并依次受到其他成员想法的影响。McCarthy 现在正视 Lisp 为带有 Algol式语法的一个编译语言，但是它的第一个原型 Lisp I，有着非常不同的风味。

Lisp“稀少的”语法结构和解释性本质是非常偶然的发展出来的。我们对这些事件的讨论遵循 Stoyan (1980) 给出的细帐。在 1958 年晚些时候 McCarthy 获得了在 MIT 电子工程系的一个助理教授职务。与 Minsky 一起，接着是一个数学助理教授，他建立了“MIT 人工智能计划”，配备了 2 个程序员，1 个秘书，1 个电传打字机和 6 个学生(其中有 Kleinrock、 Bobrow 和 Slagl - [Stoyan (1980), 165])。 这个小组开始从事写 Lisp 编译器的一个适度的尝试，但是 Fortan 计划报告的 30 “人年”使完全实现好象是一个不可完成的目标。最初用汇编语言手工编码了一些简单的表处理函数和圆括号包围的前缀表达式(就是 “(plus 2 2)” )用于测试。这种表示法后来被称为“Cambridge Polish”。纪念 Quine (一个(麻省)剑桥哲学家) 和 Lukasiewicz (表达式的“波兰表示法”前缀形式的发明者)。尽管实验得到了合理的进展，而递归和垃圾收集好象是小组必须最终解决的最困难的障碍，仍然没有语言的精确定义。在 1959 年 McCarthy (1960) 写了一篇论文来展示 Lisp 等价于图灵机，能作为“可计算性”的可作为替代的理论。为此他需要一个一致的表示法，可以使用符号表达式来描述 Lisp 表达式和 Lisp 函数二者。这导致了“引用”和“求值”操作符，它们最初单独的用作促成一个证明的理论工具。但是这篇论文带来了大量未预期的结果。这个计划的程序员之一，S. Russell 用汇编语言实现了“求值”，从而在编译器计划完全开始之前，提供了测试手工编码的函数的方式。为了以解释性方式运行这样的简单 Lisp 程序，所有表达式都必须是嵌套进去，这样程序自身成为应用于某些数据的一个表达式。幸运的是 MIT 计算实验室也介入了 MAC (Multi Access Computing)计划中；最早期的努力是使用电传终端进入分时系统中。Lisp 解释器与交换式电传终端一起使用(著名的“读，求值，打印”周期)逐渐变得非常流行。这个解释器识别的记号后来被称为“S-语言”，而第一个工作的 Lisp 系统在 1959 年 Association for Computing Machinery [McCarthy (1959)]年度会议上提出了。Lisp 1 有大约 90 个预定义函数，第一个应用例子是做初等函数的微分的一个简单例程。这个解释器马上被进一步精制和扩展为 Lisp 1.5 [140 个函数 - McCarthy (1962)]，它拥有所有后来的 Lisp 系统的“祖先”的荣耀。Lisp 1.5 迅速成为对于在 Boston 区域内从事语言转换和人工智能工作的人很有吸引的工具。当他们离开并受雇于其他地方的时候，他们经常带上一个复本，因而导致了广泛的分布。McCarthy 自己在 1962 年去了 Stanford 大学。因为他的研究转移到更加理论性的领域，而没有被牵涉到语言的进一步开发中。

Lisp 2，Algol 式的编译版本从未出现。这有很多原因。首先，在解释性上下文中 S 语言“稀少的”语法(Lisp = "Lots of Irritating, Spurious Parentheses")被证实是资产而不是债务。它使分析表达式非常的容易，因此允许快速开发嫁接在 Lisp 之上的子语言。几乎所有所谓的“AI 语言”的都以这种方式实现的，很多 Lisp 程序员猛烈的抵制介入语法糖衣的额外层。Lisp 2 死亡的另一个因素是归咎于“creeping featuritis”[Clinger (1988a), 25]。60 年代早期在 BBN(Bolt, Beranek 和 Newman)成立了一个委员会定义 Lisp 2 的特征。这导致语言规定迅速增长，为了保持“每个人”都高兴而增加新特征。实现由于财务上的限制最终被废弃了并从未复活过。在 Edinburgh 大学开发的 Pop [Burstall 等 (1971)， Burton 和 Shadbolt (1987)]，可能最接近于 Lisp 2 的样子。现代 Lisp 系统的语法同最初的“S-表示法”是一致的。McCarthy 自己总是称之为“M-表示法”[McCarthy et al. (1962)]，它也用于 Allen (1978)优秀的教科书中。Allen 称“M-表示法”为规定而“S-表示法”是表示语言。

很多基于 Lisp 1.5 的主要方言出现了。所有这些都基于一个共同祖先，但在提供的特征和工具上显示了引人注意的区别。这些不同在传统上通过叫做“兼容函数”的包来跨越，它在另一个上下文中解释一个语言的构造。当然，这种方式在计算上是有花费的，而对于支持严肃工作通常需要某种形式的“手工”转换。

定理证明(比如 SAINT 和 SIN)和代数公式操纵系统(比如 MACSYMA)方面的工作，在 MIT 的 MAC 计划导致了 MacLisp[Moon (1974)]。这个方言特别注意了数值计算的效率，这是对很多早期 Lisp 系统的常见的批评。MacLisp 自豪于一组丰富的数据类型(数组，hunk ...)，用于程序开发和调试的用户友好的环境，和一组丰富的预定义函数(大约 300 个)。它还担当了 ZetaLisp 的基础，这是用于 MIT (现在是 Symbolics)的 Lisp-机器计划[Weinreb 和 Moon (1981)]的 Lisp 版本。“标准” Lisp 和它的后代 “可移植”标准 Lisp [Griss 和 Morrison (1981)] 由 Hearn 和其他人在 Utah 大学设计和实现。 最初用作 REDUCE，和其他公式操纵系统的基础，它现在是 Hewlett Packard 工作站的 Lisp 方言，它的名字有某种误导，因为它明确的不是 Lisp 标准，并且也不比其他方言容易移植。

在 J. McCarthy 离开 MIT 到 Stanford 的时候，很多他以前的研究生被其他大学和研究机构雇佣。Bobrow 两兄弟工作于 Bolt, Beranek and Newman，一个美国研究公司。D. Bobrow 加入了在 California 的 Xerox Palo Alto 研究中心(PARC)。一段时间内在这两个机构都维持着一个联合开发的 Lisp 系统(Interlisp - Teitelman (1974))。Interlisp 也用在 Stanford 大学，在这里它成长为今天能获得的最复杂的 Lisp 系统(大约 600 个预定义函数)，带有大量的工具和被认为最用户友好的环境[Sandewall (1978), Teitelman 和 Masinter (1981)]。这个系统的一个更新版本(Interlisp-D)后来在 Xerox “Lisp 机器”上(就是 Dandelion, Dorado 和 Dolphin)，还被移植到 Siemens 和 IBM 设备上。

Bobrow 两兄弟的第二个，R. Bobrow，最终担任 California 大学在 Irvine (UCI)的教师，在这里他开发了 UCI-Lisp [Meehan (1979)]，这是在很多研究机构流行的方言。在很多年中 UCI-Lisp 充当 Carnegie Mellon 大学的 AI 程序的主要编程工具。

自从捐赠了第一个 PDP6 到 MIT 的计算实验室，DEC10 行列的机器在整个世界成为 AI 研究的标准设备； 同样的，Lisp 被控制为一个编程工具。这种现象可以部分的由它被设计为一个真正分时机器的事实来解释，当时多数其他厂商的设备仍是面向批处理的。快速人/机交互被强制为支持 AI 的典型编程风格。另一个起作用的因素在于主要的 AI 中心(MIT、Stanford、Carnegie Mellon、Edinburgh)使用这些机器用于他们大批的工作的事实；使得要运行他们的软件的拷贝就必须是选用 Lisp，而它又是自由发布的。在七十年代后期和八十年代的 Unix 操作系统的流行日益增长，仍然在 DEC 的小型机行列上产生了大量的 Lisp 实现。 PDP11 Lisp，再次基于 MacLisp，在 Harvard 开发出来。当它的一些职员去 California 大学 Berkeley 分校的时候被拿到了美国西海岸，这里已经对 Unix 有了强烈的兴趣。FranzLisp [Foderaro (1979)]是最终出现的方言。它是基于 Unix 的并运行在 VAX 和其他在大学环境流行的机器上(比如 Suns, ...)。它的持续流行很大程度归功于它的低大学使用价格。

最近在标准化上的兴趣复兴了，很大程度上受使用 Lisp 作为专家系统开发工具的刺激。很多主要计算机厂商委托设计叫做 Common Lisp 的“标准” Lisp 变体[Steele (1984)]。“最初的目标是规定足够接近 MacLisp 后代家族的每个成员的 Lisp，保证这些实现乐于朝向这个公共定义来发展自身。... 委员会的一个主要的子目标是用这个 COMMON LISP 写的程序可以实现直接的源码-可传送，而不用管下层硬件” [Brooks 和 Gabriel (1984), p. 1]。迄今为止这个计划好象成功了。现在已经存在了很多实现。但是，仍有待观察对规整 Lisp 以前不受限制的“特征”增加的尝试是否最终会成功[Allen (1987)]。仍有怀疑的余地，因为多数 Lisp 程序员是高度个人主义的，在风格问题上带有强烈的信念，因为 Lisp 使实现“新”特征非常容易。已经有对 Common Lisp 的大小和它的更加不可思议特征(经常包括它们来确保与过去兼容)的普遍批评。但是，这是一个好机会，商业压力将至少导致一个公共基础，更加专门的方言或子集可以萌发于此，还有一个希望，反映在朝向 ISO Lisp 标准的努力上。

新出现的方言之一是 Scheme，一个词法作用域版本的 MacLisp(象 NIL, T, ..)。Scheme 在 MIT 用来讲授计算机编程的介绍性课程，并在 Abelson 等人(1985)的一本优秀的书中被加以良好的文档。从作者的观点看来 Scheme 是一个非常有表现力的和优雅的语言，围绕着一个简单的小核心，准备了正交性和非常灵活的特征。嵌入到适当的交互编程环境中，它在实践上反击了通常针对 Lisp 的所有批评。它唯一的缺点在于缺乏与传统的 Lisp 系统特别是 Common Lisp 的兼容性。

并行处理近些年已经成为主要的研究焦点，由此产生了很多语言提议。MultiLisp [Halstead (1985)] 是一个有趣的基于 Scheme 的例子。

用 Scheme 编程

Posted-Date: Mon, 6 Jul 87 07:46:39 EDT
Date: Mon, 6 Jul 87 07:46:39 EDT
From: Tigger@Hundred-Acre-Woods.Milne.Disney
To: ramsdell@linus.uucp
Subject: Scheme

关于 Scheme 的美妙的事情是:
Scheme 是一个漂亮的东西。
复杂的过程式的想法
可以通过简单字符串来表达。
它清晰的语义，和缺乏书生气，
有助于使程序运行，运行，再运行!
然而关于 Scheme 的最美妙的事情是:
用它编程很好玩，
用它编程太好玩了! [Ramsdell (1987)]

概述

Scheme 由 G.J. Sussman 和 G.L. Steele Jr. (1975)在 MIT 设计和实现，作为理解计算的演员模型努力的一部分[Hewitt (1977)]。它是小而紧凑的语言，但是它的概念可以按高度正交性的方式组合和扩展。

C-Scheme [MIT (1984)] 是最初 MIT 实现的最新版本。Scheme 311 [Clinger (1984)] 在 Indiana 大学开发并最终演化成 Chez Scheme [Dybvig and Smith (1985)]。Scheme 84 [Friedman et al. (1984)] 是 Indiana 大学的另一个 Scheme 计划，主要用于实验新颖的控制结构；比如“引擎”概念。T [Slade (1987), Rees et al. (1984)] 是对效率由特殊强调的一个扩展的 Scheme 系统。它是在 Yale 大学开发的。所有这些实现都设计为运行在基于 Unix 的系统上，特别是在 Vax 和 Sun 计算机上。编程通常由标准的编辑器来支持，比如 Emacs，并有一些简单的实用工具用做错误跟踪和调试。针对个人工作站的实现通常提供更加方便的程序环境。PC-Scheme [Bartley and Jensen (1986), Wong (1987)] 在 Texas Instruments 写成，用于 IBM PCs 和 DOS-兼容微机。它包括一个 Emacs-式样的编辑器(Edwin)和一个简单的调料包(Scoops)。MacScheme [Semantic Microsystems (1986), Hartheimer (1987)] 为 Apple MacIntosh 提供一个集成的 Scheme 环境。

Rees & Clinger (1986) 的“Revised Report on Scheme”担任了标准，并被推荐为一个卓越的、简明的和非常可读的语言定义。在本书中的多数程序用 MacScheme、PC Scheme、ChezScheme 和 T 测试过了，尽管 MacScheme 被用做主要的开发工具。出于对可移植性的关心，尽可能的避免了非本质特征。

与其他 Lisp 方言形成对比，Scheme 支持显式的变量定义和词法作用域。语言提供“尾部递归”的高效实现，并提供“续体(continuation)”来定义新的控制结构。所有 Scheme 的对象被作为“一等公民”来对待，这意味这没有武断的限制对象可以做什么和它们要用在那里。任何一类对象可以赋值为变量的值，传递为给过程的参数，返回为一个结果，和存储在复合数据结构中。依据这个定义在多数其他语言中过程被明确的作为“二等公民”对待，包括 Lisp 的早期版本。Clinger (1988b) 提供了对这个概念的深度讨论。

表示和解释 - 符号 & 值

词法作用域和一级过程的组合培养强调模块性和数据抽象的编程风格。Scheme 程序可以看作一组嵌套的表达式，可能引用到一些定义，而这些定义自身可能包含更多的表达式。每个表达式都关联着一个环境，它定义“在作用域中”所有绑定。

    (define MeaningOfLife 42)
    (+ MeaningOfLife 7)

例子是有两个表达式的一个“程序”，其中第一个表达式把系统提供的 define 过程应用到一个标识符和作为它的参数的一个值。

在下面的讨论中，我们将使用粗体字来标记被系统以某种预先定义的方式使用的所有标识符。对所有的系统响应前导上一个分号(;)。在我们把精力转移到这个程序的执行之前，还要注意一些其他事情。Scheme 对标识符不做长度限制。它们必须开始于不能开始数字的一个字符，并可以包含任意树木的字母、数字和所谓的“扩展字母表字符”字符。* / < = > ! ? : $ % _ & ~ ^ 被作为这种扩展字母表字符对待。一些标识符充当语法关键字而不应当用做变量。注释开始于一个 ; 并延伸到行结束。它们被解释器所忽略。还有一个语法惯例，所有重新绑定变量的过程应当以 ! 结束，而以 ? 结束的所有过程都返回 #t 或 #f (用做“真”和“假”)。

Scheme 解释器以 Lisp 的经典的“读，求值，打印”周期的方式操作；就是说，它将读一个表达式，尝试求值它，并显示结果。在执行期间假定，除非被引用，否则把原子求值为它们的绑定，并且表结构指示函数对参数的“应用” (所以叫“应用式语言”)。依据“Cambridge Polish”的惯例解释器将尝试对表的第一个元素关联上一个过程，把它应用到所有随后的参数上。

与解释器的交互通常在某种支持编程的环境中通过所谓的记录器(transcript)进行。在这里键入表达式并打印解释器的回应。通常提供编辑器层次的语法支持；比如，系统将按照键入适当的缩进定义，并且“闪烁”匹配的圆括号。这种特征对于有如此稀少语法的语言是绝对本质性的。

表达式可以被键入和求值，还可以滚动窗口的内容来查看前面交互的结果。这种外在形式(figure)也示范了 MacScheme 的 3 类菜单。File 菜单涉及建立、装载、更新和打印文件的动作，还用于退出系统。Edit 菜单与鼠标驱动的编辑器交互。它提供用来剪切和粘贴的命令，还有用来选择一个表达式“直到”匹配的左括号("pick")和强制重新缩进(表达式通常按照它们键入的样子来缩进)。Command 菜单特定于 MacScheme，而其他两个菜单类似于其他 MacIntosh 软件的 File 和 Edit 菜单。有用来求值被选择了的表达式，和用来打断和继续执行的命令。“选择”可以使用 "pick" (在 Edit 菜单中)，也可以通过在光标已经定位于表达式的最右圆括号之后按住“enter”来完成。打断一个过程的执行将调用一个调试器，而 "pause"将简单的停止这个程序。在已经修正了错误条件之后，可以使用 "Reset" 来返回控制到“顶层”来继续一个会话。MacScheme 允许我们打开最多 4 个独立窗口。其中之一将总是记录器，而其他可以提供对文件内容的编辑器。表达式的选择和求值也可以发生在这种窗口中。表达式将接着被复制到记录器中而结果值将在记录器中显示)。这通常会导致在记录器中的文本增长的非常长，所以它的内容应当不时的被“修整”。最后，因为标准的 MacIntosh 屏幕非常小，有一个命令当记录器被其他窗口掩盖的时候用来显示它。其他 Scheme 方言也提供类似的、但经常不是很彻底的东西，用做方便的程序员界面。

在上述程序被求值的时候，它将导致建立一个环境，MeaningOfLife 在其中绑定(到 42)。随后的表达式将接着在这个环境的作用域内进行一次加法，返回值“42”。还要注意所有表达式都必须产生一个值，它总是要打印出来。它通常是被求值的最后一个项目的值，当然，有时这不是想要的行为；就是说，我们可能经常希望强制解释器按字面接受某些数据。可以使用 quote 函数来获得这种效果，比如

    (quote (define MeaningOfLife 42))
    ; (define MeaningOfLife 42)

因为引用是极其常见的操作，提供了一个简写。用来减少大量的圆括号。可以使用一个前置(prime)的 (')来指示引用。

    '(define MeaningOfLife 42)
    ;(define MeaningOfLife 42)

当然，还应当有取消这种引用的方法。Lisp 的 eval 提供这种功能。与 Lisp 不同的是，这个函数不被很多 Scheme 方言所支持。这反映了使用 eval 使有选择的代码连接很困难的事实，甚至对于单独的应用程序是不可能的，而要求在执行时获得“完全的” Scheme 系统。多数时候它都不是必须的，因为通常可以用不同的方法完成同样的效果。在 MacScheme 中能获得 eval，但是我们要克制对它的使用。不恰当的使用引用和求值是程序错误的非常多产的来源，它很快就会成为对于所有初学者显见的痛苦。它对增值这些操作建造于其上的基本模型是重要的。如同汇编语言，Scheme 在数据和程序之间不加以语法上的区别。只在指定的解释上下文中决定符号的“意义”。符号要么在字面上要么通过关联(association)指示(denote)对象。在执行期间将获得符号的绑定，而数值、逻辑值、字符、字符串和向量求值为自身。

数据类型和它们的操作

Scheme 提供的文字类型有数值、逻辑值、字符、字符串、符号、表、向量和 lambda 表达式。

Scheme 提供一些简单的过程用于输入/输出操作。表达式可以装载自文件，并在这个过程期间发生求值。在必须用户交互的编程任务中可以使用 read 函数。display 将打印任何对象的值，在需要换行(line-feed)的地方可以使用换行符(newline)。

    (define LuckyNumber (read)) ; 键入 7
    ; LuckyNumber
    LuckyNumber
    ; 7
    (display LuckyNumber)
    ; 7 #t

响应最后一个表达式的 #t 是 display 返回的值。"7" 的打印作为副作用发生。尽管不是标准特征，我们将使用两个额外的打印过程来试图精简与我们的程序输出有关的大批代码。DisplayList 和 DisplayLine 接受任意数目的参数。DisplayLine 还在结束处进行一次换行。这两个过程都是系统工具箱的一部分。

    (DisplayLine LuckyNumber "is not" 13)
    ; 7 is not 13 #t

Scheme 支持三种不同的对等价的测试，它们可以应用于任何对象。eq? 定义等价的最强解释。它在 Scheme 完全不能以任何方式区别两个对象的时候返回真。eqv? 检查两个对象在“操作等价”概念上的是否一致[Rees and Clinger (1986), 13]。在多数实际上有关的情况下结果与 eq? 相同。equal? 实现一个更弱等价概念，如果对象“打印同样的东西”则为等价。

  (eqv?  (list 'a) (list 'a)) ; 它们 "看起来一样"，但是
  ;()
  (eq?  (list 'a) (list 'a)) ; 存储在不同的内存单元中。
  ;()
  (equal? (list 'a) (list 'a))
  ;#t

 Scheme 识别整数、实数和复数，可以按习惯的方式去写:
  42
  ;42
  3.14
  ;3.14
  1.0e10
  ;10000000000

提供了多数的谓词(number?, zero?, positive?, negative?, odd?, even?)，比较(=, <, <=, >, >=)，算术(+, -, *, /, remainder, exp, expt, sqrt, log, floor, ceiling, round, truncate, ...)，和三角(sin, cos, ...)函数，它们都带有明显的行为。

    (number? 7)
    ;#t
    (odd? 3.14)
    ;ERROR: Non-integer argument to function - 3.14
    (/ 3 2)
    ;1.5
    (expt 2 3)
    ;8
    (floor 3.14)
    ;3
    (round 7.7)
    ;8
    (= 7 13)
    ;()

在 Scheme 的多数实现中空表等同于 #f，这解释了为什么上面的例子返回空表。我们还可以选择最大值和或最小值，提供了很多到其他表示形式的变换(integer->char, number->string, ...)。

    (number->string (sqrt 3.14))
    ;"1.772"

这个例子还展示了表达式是可以被嵌入的，在这种情况以正常方式(“从内至外”并且“从左至右”)进行求值。优先级规则明显的是没有必要的，因为 Cambridge Polish 表示法强制我们总是提供完整的圆括号表达式。

#t 和 #f 是两个“一般的”逻辑值。出于方便任何值都可以在条件测试中用做逻辑值。在这个上下文中不是 #f 和空表的所有值都被认为是“真”。提供了一个谓词(boolean?)和一些逻辑操作(and, or, not)

    (boolean? '())
    ;#t
    (and #t #t)
    ;#t
    (or #f (< 7 0))
    ;()

字符是表示可打印的字符的对象，使用记号 #/ 作为前导。例如

    #/x
    ;120
    #/y
    ;121
    #/space
    ;32

这里的返回的数值是字符的 ASCII 编码等价。提供了谓词(char?)、一些比较(char=?, char>?, ...)和一些转换(char->integer, integer->char)过程。

字符串是包围在双引号(")内的字符序列。使用反斜杠(/)来在字符串中包含双引号，例如

    (display "the /" character delimits a string")
    ;the " character delimits a string

要在字符串中包含反斜杠必须使用另一个反斜杠来逃逸它。Scheme 提供各种创建(make-string)、谓词(string?, string-null?)、比较(string=?, ...)、选择(string-length, string-ref, substring)、变更(string-append, ...)和转换(string->list, list->string)操作符。

    (string-length "mumble")
    ;6
    (string-append "mumble " "mumble")
    ;"mumble mumble"
    (string-ref "mumble" 4)
    ;108

上面的例子展示了字符串索引开始于 0，因为 "108" 是 "l" 的 Ascii 码表示。

不是迄今为止提到了的那些符号必被引用来强制为文字解释。

    MeaningOfLife
    ;42
    (quote MeaningOfLife)
    ;MeaningOfLife
    (quote X)
    ;X
    X
    ;ERROR: Undefined global variable X

在最后的情况下，解释器尝试获得符号的值，它以前没有被绑定。因为不存在这么个值，程序停止并且可能调用一个调试器。Scheme 使用 define 来介入变量并绑定它们到一个初始值，可以接着通过(使用 set!)副作用改变它。

    (define Capnomancy "study of smoke to determine the future")
    ;Capnomancy
    (set! MeaningOfLife Capnomancy)
    ;MeaningOfLife
    MeaningOfLife
    ;"study of smoke to determine the future"

现在我们要注意 set! 可以用来改变一个符号的值，还要注意 Scheme 的“动态类型”本质将允许我们把一个数值绑定(比如MeaningOfLife 的"42")替代为不同数据类型的实例。可以使用谓词(symbol?)和变换过程(string>symbol)来操作符号。

    (symbol? (string->symbol "Capnomancy"))
    ;#t

表是 Scheme 最重要的结构，因为它们用于“数据”和“程序”二者。明显的，它们必须被引用来充当 “Lisp-材料的惰性块”[Hofstadter (1983)]。

    '(HappyMole LittleBear LittleTiger)
    ;(HappyMole LittleBear LittleTiger)

是有 3 个元素的一个(被引用的)表。去除这些引用是要惹祸的。

    (HappyMole LittleBear LittleTiger)
    ;ERROR: undefined global variable LittleTiger

Scheme 将尝试把表处理为把叫做“HappyMole”的过程应用到余下的元素。结果的错误消息再次指出 MacScheme 杂乱无序的处理表元素，因此无法找到对“littleTiger”的任何绑定。即使对所有元素的绑定都存在，求值也可能失败。

    MeaningOfLife
    ;"study of smoke to determine the future"
    ('MeaningOfLife)
    ;ERROR: Bad procedure MeaningOfLife
    (MeaningOfLife)
    ;ERROR: Bad procedure "study of smoke to determine the future"

在第一种情况下我们要求符号的当前绑定，而在第二种情况下我们尝试“执行”这个符号，在第三种情况下我们尝试执行这个符号的值。回想起来，因为表是未被引用的，Scheme 将把它解释为一个“程序”。依据 Cambridge Polish 表示法的规则，它的第一个元素应当指示一个过程。在第二和第三种情况，它实际引用到一个名字或一个数值，它们当然不能被“执行”了。

Scheme 自诩提供操作表的丰富的自带的过程。它提供谓词(pair?, null?)、构造(cons, list, append)、 选择(length, car, cdr, ... list-ref, list-tail, assoc, member, memq) 和变换(list->string, list->vector, ...)。

表在内部存储为叫做“点对”的树结构中。这种表示可以回溯到第一个 Lisp 解释器，它建造在 IBM 704 上，它的 36-bit 内存单元可以分解成所谓的“减量”和“地址”两部分。所以一个内存单元可以用来存储要么一个表元素要么两个指针。接着从元素(“地址寄存器的内容” - car)和到子表的引用(“减量寄存器的内容” - cdr)(递归的)构造表。cons 充当表构造器。它接受一个元素和一个表作为参数并返回一个新构造的表作为结果。请注意空表()，在表处理操作中充当 0 在整数算术中的那种作用。你可以通过加到零来枚举所有的数，你也可以同样的通过增加到空表来建造表。这个过程经常被称为“构造表”。即使多数实现对待 #f 与空表是一致的，在提及空表的时候使用 () 而不是 #f 是好习惯，保留 #f 用做“假”值。如果传递给 cons 两个原子，它将制作一个“点对”；就是说，“地址”指针将设置为指向第一个参数，而“减量”指针指向第二个参数。在实际编程中直接操作点对是非常少见的，通常都提供更加方便的操作符用作表的构造。list 将绑定任意多个参数到一个表结构中，可以使用 append 联接 2 个表。

    (cons 'LittleBear 'LittleTiger) ; 制作一个“点对”
    ;(LittleBear . LittleTiger)
    (cons 'HappyMole (cons 'LittleBear (cons 'LittleTiger #f)))
     ; 同图 2.12 中一样
    ;(HappyMole LittleBear LittleTiger)
    ; 或者使用更容易的方式:
    (list 'HappyMole 'LittleBear 'LittleTiger)
    ;(HappyMole LittleBear LittleTiger)
    (append '(HappyMole LittleBear LittleTiger) '(AuntyGoose))
    ;(HappyMole LittleBear LittleTiger AuntyGoose)

pair? 检查它的参数是否是一个“点对”，还可以用于测试“表身份”(listhood)。

    (pair? '(LittleTiger))
    ;#t

null? 检查它的参数是否是空表。

    (null? ())
    ;#t

对 #f 做同 () 一样处置的实现也返回 #t。

    (null? #f)
    ;#t

提供各种过程支持选择表的特定元素。car 和 cdr 是其中最重要的。使用这样的名字只有历史性的理由，现在已经完全不适用了，但是 Lisp 社区坚定的抵制朝向更有意义的任何改变(比如，head 和 tail，或 first 和 last)。当然，car 代表“地址寄存器的内容”而引用在表头部的元素。可以使用 cdr(“减量寄存器的内容”)来取回所有余下元素的子表。请注意 car 总是返回一个单一元素，而在应用到一个表的时候，总是返回一个表(可能为空)! 尝试对一个空表的 cars 或 cdrs 将导致一个错误情况，与尝试除以零是一样的。

使用car 和 cdr 的组合可以逐个处理表的每个元素。在应用到(被引用的!)表(troll hydra banshee gryphon vampire)的时候，cdr 将产生表(hydra banshee gryphon vampire)，而 car 将返回 troll。要得到第 5 个元素，我们必须调用 cdr 四次。这将返回表(vampire)，这时 car 将接者产生想要的元素。Scheme 允许这些访问函数的联接，直到第 4 层。(car (cdr (cdr ( cdr (cdr '(troll hydra banshee gryphon vampire)))))) 可写成 (cadddr (cdr '(troll hydra banshee gryphon vampire)))。容易造成“口吃”可能是改变 car 和 cdr 名字的一个勉强的理由。实际上有更方便的方式来访问表的第 5 个元素。list-ref 可用于此目的。

    (length '(troll banshee vampire))
    ;3
    (car '(troll banshee vampire))
    ;troll
    (cdr '(troll banshee vampire))
    ;(banshee vampire)
    (car (cdr (cdr '(troll banshee vampire))))
    ;vampire
    (caddr '(troll banshee vampire))
    ;vampire
    (list-tail '(troll banshee vampire) 2)
    ;(vampire)
    (list-ref '(troll banshee vampire) 2)
    ;vampire

只有最后两个例子值得说明。list-tail 通过除去前面的 n 个元素来获得一个子表，而 list-ref 返回在指定位置的元素。要注意 list-ref 从零开始计数!

还有用于查找表的一些过程。member 和 memq 将返回它的 car 是一个指定元素的一个子表。它们使用不同的过程(equal? 和 eq?)来测试等同性。请注意它们返回表的事实不防碍它们用在(逻辑值)条件中。这是把所有非 nil 值作为“真”对待的惯例派上用场的一种情况。“关联表”是一类特殊的表，它存储“键-值”绑定。它们可以被表示为有两个元素的表的表，而且 Scheme 提供一个 assoc 过程来检索一个值，它需要一个键作为参数。

    (member 'vampire '(troll banshee vampire))
    ;(vampire)
    (member 'banshee '(troll banshee vampire))
    ;(banshee vampire)
    (assoc 'LittleBear '((HappyMole vampire)
               (LittleBear banshee)
               (LittleTiger troll)))
    ;(LittleBear banshee)

Scheme 还提供一些函数来在表和字符串之间做转换。但是，它们只有有限的用处，因为 list->string 只接受字符的表，而 string->list 对一个字符串的成员生成它们的 ascii 码等价的一个列表。

    (list->string '(#/b #/e #/a #/r))
    ; "bear"
    (string->list "bear")
    ; (98 101 97 114)

向量是异类的结构，它的分量可以被改变并使用开始于 0 的整数来索引。它们的长度是它们可以包含的元素的数目，并在建立向量的时候固定了。有效的索引值位于 0 到(length - 1)范围内。使用 # 符号指示向量。

    (vector 7 "is one of" '(7 13 42) )
    ;#(7 "is one of" (7 13 42) )

是有三个分量的 3 向量: 一个数值，一个字符串，和一个表。要生成这样的向量。Scheme 提供了创建(make-vector, vector)、谓词(vector?)、选择(vector-length, vector-ref)、更换(vector-set!)和转换(vector->list)过程。

    (define Friends (make-vector 5))
    ;#( () () () () () )
    (vector-set! Friends 0 'bear)
    ;#( bear () () () () )
    (vector-length Friends)
    ;5
    (vector-ref Friends 1)
    ;()
    (vector-ref Friends 0)
    ;bear
    (vector->list Friends)
    ;(bear () () () ())

在到分量的访问必须被计算出来的应用中、向量是有用的数据结构；比如，在棋盘中移动是可以运算出来的。例如，一个象棋盘可以存储在分量是八个向量的一个向量，其中每个向量的八个分量都可以持有“棋子”或表示空方格。

导引控制流

任何编程语言都需要提供某种设施来导引程序执行的流程。这种控制结构传统上迎合三个种类：顺序、选择和重复。Scheme 表达式通常顺序的求值；最内层的表达式先于在程序外层的表达式。cond、if 和 case 将在多个可供选择的执行路径中选择某一个，还可以使用 begin 把表达式组合到一个复合结构中。

    ; 一次"化装"舞会
    (define party '((HappyMole vampire)
            (LittleBear banshee)
            (LittleTiger troll)))
    ;party
    ;和一个"猜谜游戏"
    (cond
     ((equal? (assoc 'HappyMole party)
         '(HappyMole troll))
     "moles are trolls")
     ((equal? (assoc 'LittleBear party)
         '(LittleBear banshee))
     "bears are banshees")
     ((equal? (assoc 'LittleTiger party)
         '(LittleTiger troll))
     "tigers are trolls")
     (else "bad guess ?"))

    ;bears are banshees

cond 过程将接收任何数目的条件-动作对，这里的条件将按顺序求值，如果非假，则接着导致与这个条件相关联的所有表达式的执行。总是如此，最后一个表达式生成的值将是 cond 返回的值。与 Pascal 等传统语言不同，条件的求值是“懒惰的”。这意味着只在前面的条件被证实为假的时候才进行当前的尝试。一旦找到真条件并且它的相关表达式已经被求值了，cond 立即退出。在上面的例子中对 LittleTiger 的角色的正确猜测将永远找不到。这里有可选的 else 子句在所有条件都是假的时候调用。cond 是足够强力来描述任何可能的选择。但是，出于程序员的方便，还是提供了一些额外的选择函数，因为 cond 对于很多人好象是太复杂了。

    ;查找作为‘舞会’中第一对舞伴的键的 tiger
    (if (equal? (caar party) 'LittleTiger)
      (display "tiger is first")
      (display "keep looking"))
    ;keep looking #t

if 期望三个表达式: 一个条件，一个 then 分支和一个 else 分支。如果条件产生假，则条件产生假，则执行第三个表达式(代表 else 分支)，否则执行第二个表达式(then 分支)。可以使用 begin 来定义符合表达式，因为它对于在一个分支上关联多于一个表达式经常是必须的。

    ;查找作为‘舞会’中第一对舞伴的键的 mole
    (if (equal? (caar party) 'HappyMole)
      (begin (DisplayLine "mole is first")
          (display "who's next ?"))
      (display "keep looking"))
    ;mole is first
    ;who's next ? #t

case 表达式类似于对应的 Pascal 控制结构。求值一个表达式并使用结果的值作为索引，用来从一组侯选者中做出选择。每个侯选者都被描述为选择子和相关的一些表达式的一个表，选择子(selector)必须是常量。

    (set! age 42)
    (case (+ age 1)
       ((6  ) 'excited)
       ((21  ) 'rejoicing)
       ((30 40) 'depressed)
       (else 'indifferent))
    ;indifferent
    ;Owl 的生日聚会
    (set! luckyFellow 'owl)
    (DisplayList "an ideal pet for" luckyFellow " would be a ")
    (display (case luckyFellow
            ((tiger bear mole) "dog")
            ((owl)       "tortoise")
            ((fox)       "snake")
            ((duck elephant)  "goldfish")
            (else "???")) )
    ;an ideal pet for owl would be a tortoise

递归是在 Scheme 中指定重复的最优雅和有效的方式。但是，我们将推迟查看这个概念直到讨论完过程之后。尽管能用迭代表示的任何东西都可以捕获到一个等价的递归公式中，也不管 Scheme 优化它的执行以至于在效率上没有相关的损失的事实，我可以使用 do 来描述迭代执行。在第一眼上，do 好象是某种复杂的构造。它接受一些索引变量，它们开始于某个初始值，并以指定的方式增加它们。测试终止条件，如果它返回假则接着求值它的循环体，如果循环终止，则求值一个序列的表达式并返回最后一个的值。do 的结构被示例如下。

    (do ((  ) ...)
      ; 声明变量
      (  ... )
      ;-> 跳出
      ... )
      ; 执行循环体

    (let ((friends '(mole bear tiger)))
     (do ((next friends (cdr next)))
       ((null? next) "all clean now !")
       (DisplayLine "wash " (car next))))
    ;wash mole
    ;wash bear
    ;wash tiger
    ;"all clean now !"

let 为循环的执行定义一个适当的局部上下文。注意对 friends 的绑定只在 let 的作用域内是可获得的。很多 Scheme 方言(比如 MacScheme)也为无限迭代提供了 while 表达式。因为这不是一个标准特征，我们将限定只在它显著的增加代码的清晰性的情况下才使用它。它一般很容易被递归或 do 所取代。除了跨越表达式的迭代之外，Scheme 还提供了跨越表的所有元素的迭代。

    (for-each display party)
    ;(HappyMole vampire) (LittleBear banshee)
    (LittleTiger troll) ()
    (map abs '(1 -2 -3))
    ;(1 2 3)

for-each 对一个表的所有元素应用表达式。典型的用于发挥这个过程产生的副作用的利益。for-each 返回的值是未指定的，在另一方面，把每个应用的结果写到一个表中，接着返回它。在两种情况中的过程都不需要是预先定义的过程。程序员可以提供 lambda 表达式或他自己命名的过程。

Lambda 表达式和环境

Scheme 的执行环境被表示为所谓的“lambda 表达式”。这个术语起源于 Church 的 lambda 演算(calculus)，它充当 MacCarthy 在符号计算上的某些想法的模型。Lambda 表达式开始于一个关键字“lambda”，随后式一个(可能为空)参数的列表和一个表达式序列。当 lambda 表达式应用在正确的上下文中的时候，这些表达式按顺序执行并返回最后的值。

    (lambda () "hi there")
    ;#
    ( (lambda () "hi there") )
    ;"hi there"

在第一个例子中的 lambda 表达式定义过程文字。在第二个 lambda 表达式周围包装了额外的一对括号强制它执行。Lambda 表达式可以接受固定或可变数目的参数。使用不同的语法惯例来指出需要那种参数传递机制。

    ((lambda (aFriend) ; 函数有一个形式参数: aFriend
      (DisplayLine "hi there " aFriend))
     'HappyMole) ; 调用时带有一个实际参数: HappyMole
    ;hi there HappyMole #t

这里把由 lambda 表达式表示的过程应用到作为它的参数的 "HappyMole"上。这生成一个计算，在其中 DisplayLine 把要求的字符串放置到屏幕上。#t 是最后的显示返回的值，因此它还是整个 lambda 表达式的返回值。如果你在你自己的平台上写过了这个例子，你最有可能忘记引用 HappyMole，导致 Scheme 抱怨另一个 "unbound variable"。得到正确的引用可能需要很多实践，但是不久之后它就会成为“第二天性”。

Scheme 提供两种可供选择的方式来要求可变数目的实际参数。

    ; lambda 表达式，调用时带有 3 个实际参数
    ((lambda someFriends ; 参数周围没有括号 !
      (DisplayLine "hi there " someFriends))
     'mole 'bear 'tiger)
    ;hi there (mole bear tiger) #t
    ; 调用时带有 0 个实际参数
    ((lambda someFriends
      (DisplayLine "hi there" someFriends)) )
    ;hi there () #t 

下面的所有参数都绑定到一个表(它可以为空)中并传递给 lambda 表达式。请注意我们必须提供一个不带任何括号的单一的参数来导致这种行为。如果我们想要让我们所有的参数都是可选择的，可以使用

    ; 一个强制的和一些可选的参数
    ((lambda (aFriend . someMore)
      (DisplayLine "hi there " someMore))
     'mole 'bear 'tiger) ; 三个参数
    ;hi there (bear tiger) #t ; mole 现在被绑定到 "aFriend"
    ((lambda (aFriend . someMore)
      (DisplayLine "hi there" someMore)))
      ; 没有参数
    ;ERROR: Too few arguments to procedure
    ;0 arguments supplied - 1 argument expected

这里的 aFriend 将被绑定为 mole，而所有余下的实际参数将再次被组合到一个表中并绑定到 someMore。 当然，我们现在必须提供最少一个实际参数。

Scheme 提供一个谓词(procedure?)来测试一个对象实际上是否为过程。apply 在某些情况下也是有用的，它强制一个过程在当前上下文中的应用。注意 apply 总是期望一个表作为它的单一的参数。

    (procedure? (lambda () (display "hello")))
    ;#t
    (apply (lambda (aFriend)
         (DisplayLine "hello" aFriend))
        '(mole) )
    ;hello mole #t

Lambda 表达式可以包含它们自己的对数据和过程的“局部”定义。因此它们是主要的的环境建造块， Scheme 依据“词法作用域”的概念而有层次的安排它们。使用这种环境来定义在一个计算期间的所有点上(“作用域内”)都是当前可见的对象，早期的 Lisp 系统只支持“动态作用域”，这是导致无数非常难于跟踪的程序错误的一个“特征”。

执行的嵌套上下文

除了嵌套过程 Scheme 还有一个额外的构造用来定义(临时)环境。叫做“let 表达式”(let、let*、letrec)。生成一种“块结构”(类似于 Algol 60)。let 是一个特殊的形式，它接受绑定和一个“块体”作为参数。在这些绑定定义的上下文中，在块体中包含的表达式接着顺序的执行并返回最后一个的值。let* 假定所有绑定将被顺序的建立(从第一个到最后一个)，而 let 不做这种假定。Letrec 对于相互递归的过程是需要的。

    (let ((seven 7) (thirteen 13))
      (DisplayLine (* seven thirteen)) (+ seven thirteen))
    ; 91 ; 乘法的结果
    ; 20 ; 加法的结果
    (let ((aNumber 7)
       (twiceThat (* 2 aNumber)))
     (display twiceThat) )
    ;ERROR: Undefined global variable aNumber
    (let* ((aNumber 7)
        (twiceThat (* 2 aNumber)))
     (display twiceThat) )
    ;14 #t

这里我们需要使用 let* 来使相互依赖的绑定工作。MacScheme 的 let 显然的尝试从右到左的绑定符号，因此在被定义之前就遇到了 aNumber。

过程 - 定义, 测试, 调试

绑定 lambda 表达式到标识符导出了“命名”过程的概念。典型的 Scheme 程序将包含大量用户定义的过程，通常组织到必须在程序执行之前装载的一些文件中。使用 load 过程完成这个任务。

    (load "HardDisk:cookieMonster.scm")

将尝试装载并求值在目录 HardDisk 中的文件 cookieMonster.scm 中的所有表达式。文件操纵的详情通常特定于特定 Scheme 实现。但是，习惯于对 Scheme 文件使用后缀“scm”。

我们可以“别名”任何数据类型，包括过程。它可以用来裁剪系统函数的名字来适合我们的偏好；带有额外的一层间接的代价。我们通常保护重要的系统定义的标识符不被意外的重定义。但是，对于经常需要的操作符(比如 car 和 cdr)，导致的在执行速度上的损失通常是不可接受的高。

    (define head car)
    ;head
    (define tail cdr)
    ;tail
    (head (tail '(vampire banshee troll)))
    ;banshee
    (set! + *) ; sneaky: redefine '+' as a multiplication symbol ?
    ;ERROR: Integrable procedures may not be redefined

请注意 Scheme 的绑定模型是完全一般性的。在对“被动”对象(数据)能做的事情和对“主动”对象(过程)能做的事情之间没有区别。例如，我们可以轻易的写返回另一个过程作为值的过程。

    (define GenericMagicLamp
      ; 这是一个我们希望返回的"lambda"表达式
      (lambda (noOfWishes)
       (define count 0) ;局部变量
         (lambda ()
          (if (< count noOfWishes)
            (begin
             (set! count (+ 1 count))
             'Granted)
            '(you've had all you're going to get !))
         ) ))
     ; GenericMagicLamp

GenericMagicLamp 实现了阿拉丁神灯的概念，在其中关押了一个妖魔并通过摩擦震动来释放出来。出于感激的天性，她将接着提供惯例的三个愿望，通常带有针对 meta-circularity 的某种保护(就是说，拒绝能带给你额外愿望的愿望)。我们的过程包含对一个局部变量 count 的声明，它将被初始化为零并在每次满足愿望之后增加一。在这一点上，注意到 Scheme 变量都有“无限的范围”是很重要的，这意味着，(例如)与 Pascal 中的其他变量不同，在它们在其中定义的过程的连续调用之间，它们不会失去它们的值。因此 Count 将开始于为零的一个值，在第一个愿望之后保持为一的一个值，第二次之后是二，在第三次调用之后是三。尽管 GenericMagicLamp 自身不会满足任何愿望，但是它可以用做一个发生器，用来构造任意数目的神灯，带有在创建时刻定义的愿望数目。这是嵌套在这个过程之中的第二个 lambda 表达式的作用。记住这个 Scheme 函数总是返回它们遇到的最后一个表达式的值。在这里是第二个 lambda 表达式，因此 GenericMagicLamp 是返回另一过程作为它的调用结果的一个过程。

    (define AlladinsLamp (GenericMagicLamp 3))
    ;AlladinsLamp

可以用来制造这么一个灯(一个过程)并让 AlladinsLamp 充当它的标识符。记住这个过程还继承了在创建发生的时候、它在其中建立的环境中的所有绑定变量是很重要的。Count 因此对 AlladinsLamp 是可以访问的，并且它仍被绑定为零。如果我们现在开始摩擦，我们就会得到我们期望的行为了(这些愿望的“形态”将保持私有)。

    (AlladinsLamp)
    ;granted
    (AlladinsLamp)
    ;granted
    (AlladinsLamp)
    ;granted
    (AlladinsLamp)
    ;"you've had all you're going to get !"
    (set! count 0)
    ;ERROR: Undefined global variable count
    ;hard luck - "count" is kept private to this lamp object, and can't be accessed !   

递归

递归具体化了自引用的概念，并且它是 Scheme 指定一段代码的重复执行的最有效的工具。阐明它的一般想法的一个好例子是众所周知的一个漫画，一个人拿着他自己的照片，在照片种他要年轻几岁。照片中的人依次拿着同样的照片(照片中的人拿着同样的照片 ...) 一直到“降到最底部”、照片中的人是个婴儿。

可以使用递归来以非常幽雅的方式描述结构和处理过程二者[Roberts (1986), Burge (1975)]。唯一的要求是我们可以对其使用递归的、事物的某种程度上的规律性。这种规律性必须包含在元素和它们的内部连接的本质中，它引发直接或间接的线性、层次、或网络结构。结构的递归描述是常见的。上面提及的照片就是一个例子。在科学和自然中很多结构是高度递归性的，通过它们的成长过程来探索某种规律性，在计算机科学同样业富于这种描述。考虑把二叉树规定作为“一个叶子或一对二叉树”；或把表规定为“一个空表或跟随着一个表的一个元素”。表的递归本质很容易的映射到通常处理它们的递归方式上。在图表 2.13 中展示了一种适用的情况。这里递归的调用 cdr 函数来“走”到我们感兴趣的元素那里。处理过程的递归描述在日常生活中也是很流行的。儿童的故事通常是高度递归的，而且这种描述好象非常容易理解和非常有趣(在那个年纪)。我们将查看下面的简单的例子。这种故事也非常容易“产生”(讲述)而很快变得无聊。

用数学归纳法证明的处理过程与递归描述密切相关。我们可以很非正式的把递归定义为把一个问题简化成在结构上是一致的、并某种程度上更加容易解决的一个或多个子问题的处理过程。这种想法可以接着应用到每个子问题，直到整个处理过程直到子问题的解决变得明显的的某个层次。我们可以接着“递归回溯”子问题链来把所有东西再次合到一起，所以对最初问题的解决将被构造出来。Hofstadter (1983) 给出了这种处理过程的愚蠢但有启迪意义的一个例子: “你如何做有 13 个石块的一个堆? - 放置一个石块在有 12 个石块的一个堆上。你如何做有 12 个石块的一个堆上? ..."。我们将把任务的完成留做读者的练习。当然我们必须总是小心的提供某种方式，能够预期这种描述或处理过程终止。想象一下执行了下列程序之后会发生什么 [Dybvig (1987), 37] (它的名字告诉我们不要尝试它)。

    (define GoodBye (lambda () (display ".") (GoodBye)))
    (GoodBye)

可以用迭代表示的所有东西都可以捕获到等价的递归公式中。与其他语言不同的是在 Scheme 中使用递归经常没有存储空间的处罚，因为解释器将自动的尝试把递归描述转换到一个迭代循环结构中。这总是由所谓的“尾部递归”来保证。如果在递归调用点上的一个过程的值是这个递归调用的值，则这个调用是尾部递归的。但是，如果在把这个结果“向上”传递回递归链之前对它进行了某些操作，则尾部递归不成立[Dybvig (1987), 71]。在需要对表元素的操作的重复性应用的时候，还有在其他通常使用重复结构(比如 do, for, while)的上下文中，尾部递归发生的非常频繁。因此 Scheme 的迭代过程只是充当语法糖衣。

在 Scheme 中递归最通常用于表处理。考虑一个程序，写众所周知的“Hairy MacLary”类型的儿童故事的[Dodd (undated)]一个变种。在这些故事中 Hairy McLary(一个 terrier 狗)出去散步并沿途“积累”朋友，所以在每个门口唱诵的名字表将逐渐变长。

    (define StoryTeller
     (lambda (mainCharacter someFriends)

      (define chorus
        (lambda (someFriends caravan)
         ; 检查终止
         (if (null? someFriends)
           #f
           (begin
            ; 问候一个朋友
            (DisplayLine (car someFriends))
            ; 并“罗列”所有已经加入的人
            (display "with ")
            (map (lambda (aFriend)
                (DisplayLine aFriend)
                (display "and "))
               caravan)
            (DisplayLine "...")
            ; 在另一个朋友上递归(并让这个人
            ; 加入 "caravan")
            (chorus (cdr someFriends)
                (append
                  caravan
                  ; needs a list here !
                 (list (car someFriends))) ))) ))
    ; "StoryTeller" 函数的函数体
     (DisplayLine "out of the gate and off for a walk went")
     (DisplayLine mainCharacter " ...")
     (newline)

     (chorus someFriends (list mainCharacter))

     ; we will skip some more friends here, and also their
     ; encounter with Scarface Claw (the toughest Tom in town)

     (newline)
     (display "straight back home to bed") ))
     ;StoryTeller

在做调用带有如下数据的时候，这个尾部递归过程生成下面的熟悉的故事:

    (StoryTeller
     "Hairy MacLary from Donaldson's Dairy"
     '("Hercules Morse, as big as a horse"
      "Bottomley Potts, covered in spots"
      "Muffin McLay, like a bundle of hay"))
      ; out of the gate and off for a walk went
      ; Hairy MacLary from Donaldson's Dairy ...
      ; Hercules Morse, as big as a horse
      ; with Hairy MacLary from Donaldson's Dairy
      ; and ...
      ; Bottomley Potts, covered in spots
      ; with Hercules Morse, as big as a horse
      ; and Hairy MacLary from Do