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 Donaldson's Dairy
; and ...
; Muffin McLay, like a bundle of hay
; with Bottomley Potts, covered in spots
; and Hercules Morse, as big as a horse
; and Hairy MacLary from Donaldson's Dairy
; and ...
; straight back home to bed#t
上面的程序是尾部递归的，因为我们在后续对 chorus 的调用返回之后不尝试更改它生成的任何数据。它还对展示非尾部递归的过程是有教益的。
这次我们的朋友们攒钱买一个新沙发，他们定时地希望总计他们的钱看是否已经买得起了。下面的过程做这个把戏，假定我们列出朋友和有关的财产。
(define HowMuchMoneyDoWeHave
(lambda (someFriends)
(define count
(lambda (aFriend) (cadr aFriend)))
(trace count)
; "HowMuchMoneyDoWeHave"过程的过程体
(if (null? someFriends) ; 终止条件
0
; 把它们加到一起
(+ (count (car someFriends)) ; 这个人
(HowMuchMoneyDoWeHave ((cdr someFriends))) ; 其他人的
) ))
;HowMuchMoneyDoWeHave
(trace HowMuchMoneyDoWeHave)
; #t
下面的跟踪展示在程序执行期间递归是如何展开的。跟踪功能不是标准的 Scheme 特征，但多数方言都提供了这种设施。
(HowMuchMoneyDoWeHave
'((HappyMole 3) (LittleBear 1) (LittleTiger 0)))
将打印:
; 递归“进入”表
Computing (#
((happymole 3) (littlebear 1) (littletiger 0)))
Computing (#
((littlebear 1) (littletiger 0)))
Computing (#
((littletiger 0)))
Computing (#
())
; 终止条件满足了，
; “回绕”这个递归 (做我们要的总计)
(# ()) --> 0
Computing (# (littletiger 0))
(# (littletiger 0)) --> 0
(#
((littletiger 0))) --> 0
Computing (# (littlebear 1))
(# (littlebear 1)) --> 1
(#
((littlebear 1) (littletiger 0))) --> 1
Computing (# (happymole 3))
(# (happymole 3)) --> 3
(#
((happymole 3) (littlebear 1) (littletiger 0)))
--> 4
; 4
运气不好，沙发价值 10 个金币，他们仍不能买一个。如同预想的那样你不能太依赖 tiger。他对金钱没有什么想法。
额外特征
本节总结对 Scheme 的简要介绍。尽管多数 Scheme 的主要特征已经被覆盖了，没有空间做更多的风格讨论了。我们故意把我们的处置限制在据信是 Scheme 的本质的和可移植的那些方面。Rees 和 Clinger (1986)给出这门语言的完整定义。有些额外的标准特征，特别是在数值和输入/输出操作领域中。概念，比如引擎[Dybvig (1987)，Hayes 和 Friedman (1984)]，宏和语法扩展[Dybvig (1987)]没有提及；主要是因为仍然缺乏这些概念的标准实现，尽管很多方言已经提供了一些这种设施。请注意本书不意图充当参考手册的替代品。因此我们强烈建议使用你工作用的方言的参考手册，接着继续你的探索。
编程是需要实践的一种技巧，特别是对于“良好”风格的开发。读其他人写的程序是特别重要的，然而写你自己的程序和从你的错误中学习是生死攸关的。
Scheme 好象特别适合于这种业务，因为它带给用户的不只是编码解决某些问题，还有寻找特别优雅的公式表达。Friedman 评论一个良好的计算机语言为：“应当提供一个环境，程序可以在其中为手头的问题创造性生成计算模型或范例。程序员构造范例的能力不应当受到限制。我把易于构造范例称为语言的“易范例性”(paradigmicity)。有低易范例性的语言是讨厌的。...我们如何建立有高易范例性的语言呢? 我们介入一些基本概念，组合这些概念的一些方式，并且这么做的过程中我们利用了解决问题的多年经验。在现存的语言中没有那个比 Scheme 更易范例性了。它的基本概念是过程、续体、引擎、条件和赋值语句。所有东西都会合在复合和递归下，它预备了语法和语义扩展二者。... 使用这些基本概念的实验和实践的越多，新范例出现的越快。” [Friedman in: Dybvig (1987), preface]。
对风格的一些建议
Scheme 是一个高度交互式的语言，它带有鼓励试探性风格的问题解决的特征。这种属性使学习过程变得容易。新的想法可以立即实验，它担当使困难的概念非神秘化的任务要比任何“静态”的描述形式要好。表结构用来表示数据和程序二者。因为它们还强调了有层次的嵌套和递归，这鼓励了“块状”的应用程序和创造分层设计。
有一些基本规则用来写有良好结构的 Scheme 程序，多数这些规则类似于在典型的 Lisp 教科书中给出的指导方针。Abelson 等人(1985) 的书和在本书中讨论的工具箱程序可以充当有代表性的例子。
过程定义应当简要，并且它们应当面向一个单一的、定义良好的目的。任务应当尽可能的分解到一些子任务中，如果它们延伸超过了一页，把它们委派给其他过程。过程还应当围绕概念来组织，概念依次反映在正确的数据结构中。这个要求演化自分层设计的方法论，强烈建议使用它。创建、查询、选择、显示和更改过程的概念给出对通常需要那种过程的指导。
程序应当是可读的和易于理解的。这个原理对标识符命名和程序构造方式有明显暗示。标识符应当是描述性的，并且它们应当提供与所表示的概念有关的助记符。还希望你遵从分类标识符的特定格式惯例。例如，我们使用大写字母来开始工具箱过程的名字，而小写字母用作系统定义的过程的名字。Scheme 使用特殊的后缀: "?" 用于谓词(就是返回 #t 或 #f 的函数)和 "!" 用于有“副作用”的所有过程(就是说，改变对非局部变量的绑定)。因为 Scheme 是一个动态类型的语言，参数的命名应当反映它们的值。使用 aNumber 或 anAList 替代 n 或 l。尽管你可能开始时憎恨键入长名字、并可能感觉你的程序过于冗长了，额外的努力以后会得到报答的。
在你的程序中使用清晰的结构将要求某些决断力，而你将最终发展出一种你自己的风格。完成这个目标的唯一方法是阅读和评判其他人的代码，并采纳你喜欢的到你写的程序中。因为这种决定通常涉及感性，除了维持一致性之外，不能给出一般的规则。不要惧怕实验。如果你觉得增进了的理解能使你做出更好的工作，抛弃老的程序并再次开始。
递归和表结构在编程符号应用中同迭代和数组在数值应用中一样常见。尽管你需要做有意识的努力来克服所有 Pascal 或 Fortran 条件反射，你应该使用它们发挥它们的全部优势。递归是定义和处理重复和有规律结构的“自然的”和优雅的方式，并且这种结构很易于表示为表。
set! 过程可能产生“非局部”的副作用，所以它有害于一个程序的可理解性。这导致一些人完全反对它的使用并鼓吹没有任何副作用的“纯”函数式编程。在处理过程要按照复杂的状态变化来描述的情况下，这种风格经常是非常不实际的，所以作者不赞同这种推理。改变值绑定的能力是非常有用的工具，它的作用不能总是很方便的用任何其他方式完成。你应当尽可能的细心的保持这种绑定的作用域为局部，并适当的加以文档。在很多情况下，let 表达式、嵌套过程调用和递归能导致更清晰的结构。
深度嵌套的 cars 和 cdrs 经常是难于理解的，因此应当避免。处理这种深度递归结构的更加可取的方法是使用多层解释，这样 car 和 cdr 的长链就变得不需要了。例如，(GetXCoordinate (GetFirstPoint (GetBottomEdge (aTriangle)))) 比 (caar (caddr aTriangle)))更可取。使用适当的选择子(selector)函数也会使你的程序更加灵活并更易于维护。对象封装的实质性利益也应当探究，因为使用这种象征(metaphor)有助于使你的程序更加健壮和安全。
象很多其他强力特征一样，续体可能是危险的工具。尽管它们在某种程度上比“go to”语句相关的想法更加“安全”，它们的正确使用在相当大程度上要求程序员方面的自我约束。对“why”、“what”、“where”和“how”加以适当的文档也是基本的，更甚于更简单的结构。因此续体应当保守的使用，用来实现其他方式不能实现的目标。即使你不应当以它们的“原始”形式使用它们，但是应当把它们看作组合适当的高层结构的建造块(比如，非局部 escape, 协同例程 ...)。
Scheme 的交互式本质允许你在过程写完之后立即测试它们。你应当完全利用这种可能性并运行一组选择的测试个例，有效的和无效的二者都要有。
在编程风格上的多数一般指导方针也适用于 Scheme 程序。Kernighan & Plauger (1974) 和 Ledgard (1974) 给出了一个良好的总结。
程序应当适当的缩进和注释，尽管使用适当的标识符和有可能迅速的测试过程减少了注释的数量但它们仍是需要的。过程的定义通常应当开始于一个对它功能的简要解释，如果从它的名字看来不是很明显的。在复杂的应用中还应当有对类型、结构和这个标识符用途的描述。除了这些考虑之外，应当使用注释来突出一段代码重要的部分。它们应当经常是解释性的(就是说，在做“什么”)而不是纯描述性(就是说，是“如何”完成的)。缩进应当是一致的并应当强调程序的结构。因为嵌套的过程的清单有着一种不幸的倾向，它会溢出页面的右侧，在任何 scheme 缩进之下，都经常需要行使某些调整，在一致性和美观性之间作出权衡。
所有信息都应当尽可能的模块化和局部化。全局变量应当非常保守的使用! Scheme 支持局部变量和局部过程，你应当使用这些设施来把信息装载到正确的模块中。例如，任何只在另一个过程内部调用的过程都应当嵌套到那个过程中。作为它的逻辑上的结论，这导致了面向对象结构，尽管有些事例中过程是简单的，在其中使用与面向对象有关的额外的“脚手架”是不正当的。
因为 Scheme 用作讨论很多重要的编程象征的一个工具，本书后面的章节将提供给出近一步提示和察看这些建议应用的充分机会。
总结和看法
Lisp 是围绕符号操纵的想法建造的。原子和表是它的基本结构建造块。每个对象要么是一个表要么是一个原子。表可以递归的定义，所以可以有表的表的表 ...，形成任意复杂的树结构，表和原子可以被求值为要么数据要么是所谓的 lambda 表达式。事实上，Lisp 解释器将求值它遇到的所有东西，除非被显式的引用了。
Lisp 是一个应用式和基于表达式的语言，这意味着解释的主体单元是圆括号表达式。“纯” Lisp 禁止“副作用”。这个限制经常被证明是过分限制、并且实际语言在很大程度上屏弃了它。所以 Lisp 通常不能被当作函数式语言。需要介入赋值的正确决断必须处理好模块化的问题，这超出了本文的范围。Abelson 等人(1985) 的书的第三章是详细分析的好来源。Lisp 表达式可以引用其他表达式，要么直接的要么通过把某种函数应用到参数。每个对象，包括函数，可以动态的构造和操纵；所以我们可以有返回函数的函数，改变函数定义的函数，等等。存储管理是自动进行的。对对象没有类型限制，但程序员可以通过选择适当的标适符来细心的介入(数据)结构。尽管为变量声明关联上数据类型通常被认可为编译型编程语言的重要特征，它在解释性环境没有多大用处。它的主要用处在于使编译器可以优化存储和执行，并对程序做一致性检查。解释器动态的建立数据结构，所有优化并不重要。自动的一致性检查可能使需要的，但是因为程序员在程序失败的时候有权访问所有绑定的来源和值，错误预防通常不象编译环境中那么关键。它可以被高级的错误检查和更正特征所取代。当然，效验和优化一个已经稳定了的程序仍使非常需要的。
递归和条件表达式合起来是 Lisp 的主要控制结构。这是恰当的，因为它允许容易的和优雅的定义重复的规则的结构。在常规计算机体系上递归的低效一直是对 Lisp 的主要批评之一。尽管这种讨论直到几年前还是有益的，现在在很大程度已经被新的实现技术和专用“Lisp 机器”的出现所克服，Lisp 机器在微程序级别支持表和递归，但是，仍然可以公平的说使用 Lisp 经常会导致“内存饥荒”的程序。
Lisp 是一个交互语言，支持试探风格的程序开发。结构编辑器和复杂的调试工具通常作为它所嵌入的编程环境的一部分。这使编写 Lisp 函数的任务非常容易，而不用管众所周知的那些错综复杂的圆括号。结构编辑器可以帮助圆括号恐惧症患者战胜 Lisp 稀少的语法带来的多数缺点。
很多其他经常引证的缺点(比如，动态作用域，缺乏“块结构”，单一的数据类型，低效的数值操作和计算效率)已经在新方言中以各种方式去除了。
尽管很多年过去了，仍然只有不多的讲授用 Lisp 编程的教科书，这种情况最近已经戏剧性的改变了。现在已经有了针对不同方言的、对不同背景的读者广泛的教科书。Siklossy(1976) 的书使最老的一本。它很大程度上限制自身到 Lisp 1.5 已经介入的那些特征。Allan(1978) 仍是一本出色的技术性介绍，使用“M-表示法”使它很大程度上独立于任何特定方言，它还包含了对实现要点的一个可靠的讨论。但是 Allen 的教科书对没有先前的编程经验的学生可能是不可企及的，Touretzki(1984) 和 Hasemer(1984) 写的书明确的针对这种“初学者”。Wilensky (1984) 是更加面向技术的另一个有趣的教科书。这本书有两个版本可获得；一本基于 FranzLisp 而另一本基于 Common Lisp。Winston 和 Horn(1984) 强调 AI 应用。他们的书是 Winston(1984) 的伙伴并且被重写了来确保 Common Lisp 兼容。Tanimoto(1987) 是关于 AI 方法论的一个新近的教科书。同很多这种教科书一样它包含一个优秀的、但必须是简要的对 Lisp 的介绍。最后， Charniak 等(1980)写一本教科书，基于 UCI Lisp，对于 AI 编程技术给予高级的对待，它的一个新版不久就会出版。Abelson、Sussman 和 Sussman(1985) 仍是关于 Scheme 的最重要的教科书。Friedman 和 Felleisen(1986) 和 Eisenberg(1987) 提供一个要求更少的介绍。Dybvig(1987)，ChezScheme 的开发者，写带有一些更充实的例子的一本教科书，在其中他还覆盖了如引擎和语义扩展这样的特征。有一个活跃的 Scheme 用户组通过在 MIT(uucp: Scheme@mc.lcs.mit.edu)的邮件列表交流。