第一章 简介

Scheme是一种通用编程语言。它是一种高级语言，支持字符串、列表、向量这样的结构化数据，以及数字、字符这样的传统数据。虽然Scheme通常被用于符号运算，但得益于丰富的数据类型集和灵活的控制结构，它可以说是一种真正的通用语言。Scheme已被用来编写文本编辑器，优化编译器，操作系统，图形处理，专家系统，数值运算，金融分析，虚拟现实系统和几乎所有可以想到的程序类型。scheme非常简单，因为它只基于少数语法形式和语义概念，而且大多数实现都能交互，鼓励用户去尝试。但scheme也很难，想发挥其全部潜能，离不开钻研和实践。

在同一实现下，scheme程序可移植性很强，因为底层几乎完全被隐藏了。scheme也可以在不同实现间移植，这归功于一群语言设计者的共同努力，他们发表了一系列报告，称为Revised Reports on Scheme，简称RnRS。最新的第6版报告，即R6RS，强调要借助标准库和标准机制，定义新的可移植库和顶层程序。

尽管一些早期实现效率低下，但是许多基于编译器的新实现都很快，可以与低级语言相媲美。有时仍然存在的相对的低效率，那是因为运行时的检查，它们支持通用运算，能帮程序员检测、纠正各种常见的错误。在许多实现中，都可以禁用检查。

Scheme支持多种类型的数据，或者说对象 ，比如字符，字符串，符号，列表和向量，以及所有数字类型，包括复数、实数和任意精度有理数。

程序会根据需要，动态分配储存空间来存放对象，并保留空间，直到不再需要为止，然后使用垃圾回收器，定期回收无效对象的空间。简单的原始值，例如小整数，字符，布尔值和空表，通常表示为立即数，因此不会产生分配或回收的开销。

不论怎么表示，所有对象都是第一类对象，又称为头等公民。因为他们可以永久保留，所以可以作为参数自由传递，作为返回值形成新对象。这与许多语言形成鲜明对比，它们的复合数据——比如数组——是静态分配的，而且从不释放，在代码块的入口分配，在出口无条件释放，或者由程序员手动分配或释放。

Scheme是一种传值调用的语言，但是至少对于可变对象，值储存的是地址。但这些地址被隐藏起来了，程序员不需要知道这些，只需要知道的是，当一个对象被传递或者返回时，并没有复制对象，只是传递了地址。

Scheme的核心是一个很小的语法内核，是所有其他语法形式的基础。这些核心形式、派生的扩展语法形式以及一组原始过程共同构成了完整的Scheme语言。Scheme的编译器或者解释器可以很小，并且有潜力做到高效而可靠。许多拓展的语法形式和原始过程，都可以在Scheme本身中定义，这简化了实现，提高了可靠性。

Scheme程序和数据结构共享通用的表示形式。结果是，任何Scheme程序都可以自然地作为对象。例如，变量和关键字都用符号表示，结构化语法形式用列表表示。这些表示形式是Scheme语法扩展功能的基础，可以根据现有语法形式和过程，定义出新的语法形式。它还有助于用Scheme实现自身的解释器、编译器和其他程序转换工具，包括其它语言的程序转换工具。

Scheme的变量和关键字使用词法作用域，Scheme程序使用块结构。标识符可以导入到程序或者库中，也可以被局部绑定到给定代码块内部，比如库、程序或者过程体内部。局部绑定只在特定的代码块中可见。同名标识符如果出现在代码块外部，则指向不同的绑定，如果在外部没有绑定，那么外部的引用无效。代码块可以嵌套，并且内层的绑定可以屏蔽外层的同名绑定。一个绑定的作用域，是该绑定所在的代码块减去屏蔽该绑定的内层代码块。模块化程序用块结构和词法作用域构造，容易阅读，维护简单，而且可靠。用词法作用域的代码可以很高效，因为编译器可以在执行程序之前，确定所有绑定的作用域，解析出每个标识符引用的绑定。当然，这并不并不是说编译器能确定所有变量的值，因为除非执行程序、计算变量，它们在大多数情况下都是未知的。

在大多数语言中，过程的定义只是简单地关联过程名和代码块，代码块的局部变量就是过程的参数。在有些语言里，过程可以在另一个过程或代码块中定义，但只能在封闭的代码块被执行时才能调用。在另外一些语言，过程只能定义成全局的。对于Scheme来说，过程可以定义在另一个过程或者代码块中，在定义后可以随时调用，甚至在外层代码结束之后也没问题。为了支持词法作用域，Scheme的过程携带了词法上下文（环境）。

另外，Scheme的过程不是都有名字。它的过程是第一类数据对象，和字符串、数字一样，变量可以像绑定其它数据对象一样绑定过程。

和大多数语言一样，Scheme的过程也可以递归调用，也就是说，过程可以直接或间接的调用自己。很多算法用递归的方式来实现，会更优雅、更高效。有一种特殊的递归，叫做尾递归，它用来实现迭代——或者说循环——算法。尾递归发生在过程直接返回调用另一个过程的结果时，或者是过程直接或间接的尾调用自己时。Scheme的实现需要将尾调用实现为跳转，即goto，这样可以避免和递归相关的内存开销。

通过continuations，Scheme可以定义任意的控制结构。continunation是一种过程，在给程序中给定的位置声明程序剩下的部分。可以在程序执行的任意时刻捕获continuation。和其它过程一样，continuation也是第一类数据对象，可以在创建后随时调用。不管什么时候被调用，程序都会立即从捕获它的位置开始执行。通过continuaion，可以实现复杂的控制机制，包括回溯，多线程及协同程序。

在Scheme中，通过编写转换过程，确定每一个新的语法形式如何映射到现有的语法形式中，程序员可以定义新的语法形式，或者说语法拓展。这些转换过程可以用Scheme写，这得力于Scheme是方便的高级模式语言，可以自动执行语法检查，解析输入并重新构造输出。默认情况下，转换过程保持词法作用域，但是程序员可以控制所有标识符在转换后的作用域。语法扩展很有用，可以定义新的语言结构，用来模仿其它语言里的语法结构，从而达到内联代码的效率，甚至用Scheme模拟整个语言。大型的Scheme程序一般混合使用语法扩展和过程定义。

Scheme从Lisp语言演化而来，是Lisp的方言之一。Scheme从Lisp那里继承了许多东西：将值作为第一类对象的处理方式，一些重要的数据类型——包括符号和列表，将程序表示为对象等。词法作用域及块结构继承自Algol 60[21]。在Lisp的方言中，Scheme第一个支持词法作用域、块结构、第一类过程、尾递归、continuation，以及词法作用域限定的语法扩展。

Common Lisp[27]和Scheme是Lisp的现代方言，并且相互影响。Common Lisp像Scheme一样，不同于以前的Lisp语言，采用了词法作用域和第一类过程，不过它的语法扩展不遵守词法作用域。Common Lisp对过程的求值规则和其它对象的规则不同，它在一个单独的命名空间里维护过程变量，从而限制了将过程作为第一类对象。Common Lisp也不支持continuation和尾调用，但是它支持几种Scheme没有的控制结构。这两种语言比较相似，Common Lisp有更多专门的结构，而 Scheme包括更多通用模块，可以构建各种结构。

本章剩下的部分描述Scheme的语法、命名规约，以及贯穿与本书中的排版规则。

1.1 Scheme语法

Scheme程序包括关键字、变量、结构形式、常数（数字，字符，字符串，带引号的向量，带引号的列表，带引号的符号等）、空格和注释。

关键字、变量和符号统称标识符。标识符可以由字母，数字和某些特殊字符组成，包括？ ！ 。 + - * / < = > ： $ ％ ^ & _ 〜 @，以及其它Unicode字符。标识符不能以@符号开头，也不能以任何前面可以加数字的字符开头，例如，数字，加号，减号或者小数点。加号、减号、省略号和以->开头的是例外，它们都是有效的标识符。例如，hi,Hello,n,x,x3,x + 2,？$&* !!!都是标识符。标识符由空格、注释、括号、方括号、字符串、引号、双引号、井号分割。分隔符或者其它任何Unicode字符都可以被转义为\xsv;的形式，其中sv是字符的十六进制标量值。

Scheme标识符没有长度限制；程序员需要多长就能写多长。然而，长标识符不能替代注释，频繁使用会使程序难以排版，不好阅读。一个好的原则是，当作用域较小时，用短标识符，而当作用于大时，用长标识符。

标识符可以大小写混用，并且区分大小写，也就是说，即使两个标识符仅在大小写上有所不同，它们也不一样。例如，abcde，Abcde，AbCdE和ABCDE都是不同的标识符。这跟以前的标准不同。

结构形式和列表常量括在括号里，例如(a b c)和(*(-x 2)y)。空列表被写为 ()。 匹配的中括号[]可以代替括号，通常用于某些标准语法形式的子表达式，可以提高可读性，整本书中的示例就是这样写的。向量的写法与列表类似，不同之处在于，向量之前带有＃，例如＃（这是符号的向量）。字节向量被写为无符号字节值（在0到255之间的整数）的序列，并用＃vu8(和)括起来，例如＃vu8(3 250 45 73)。

字符串用双引号引起来，例如"I am a string"。字符以＃\开头，例如＃\a。在标识符中时，字符符常量和字符串常量的大小写很重要。数字可以写为整数，例如-123，也可以写成分数，如1/2，写成浮点数或者科学计数法，如1.3或者1e23，或者写成以直角坐标系或极坐标表示的复数，例如1.3-2.7i，-1.2@73。在数字的语法中，大小写并不重要。布尔值代表真和假，写成#t和#f。在Scheme的条件表达式中，#f为假，#f外的其他对象都为真，所以3,0,(),"false",nill都为真。

在第6章的各个部分，以及从455页开始的Scheme的正式语法中，有每种常量语法的详细信息。

Scheme表达式可以跨行，不需要显式终止符。因为表达式之间的空白字符（空格和换行符）并不重要，应该缩进Scheme程序代码，展示代码结构，从而增加可读性。注释可以出现在Scheme程序的任何一行，在分号和行尾之间。解释特定表达式的注释通常放在同一缩进级别上，写在表达式的前一行。解释过程或一组过程的注释通常放在过程之前，不缩进。前面通常使用多个注释字符，例如;;; 下面的过程...。

Scheme也支持两种其他形式的注释：块注释和数据注释 (Datum Comments)。块注释用＃|和|＃分割，并且可以嵌套。数据注释由前缀＃;和要输出的数据组成。数据注释通常用于注释单个定义或表达式。例如，(Three #;(not four) elements list) 。数据注释也可以嵌套，#;#;(a)(b)把(a)和(b)都注释了。

某些Scheme值，例如过程和端口，没有标准的输出形式，因此在程序的输出语法中永远不会显示为常量。在显示返回这类值的过程的输出时，本书使用了符号＃<description>，例如＃<procedure>或＃<port>。

1.2 Scheme命名规定

Scheme的命名规定很有规律。下面是命名规定：

• 以问号结尾的谓词，代表返回正确或错误的过程，例如eq?，zero?和string=?。常用的数字比较符号=,<,>,<=,>=是例外。
• 类型谓词，例如pair?，由类型名加上问号组成。
• 大多数字符、字符串和向量过程的名称，都以前缀char-，string-和vector-开头，例如string-append。某些列表过程的名称以list-开头，但大多数不是。
• 类型转换过程的名称写为类型1->类型2，例如vector->list。
• 有副作用的过程和语法形式的名称以感叹号结尾。比如set!和vector-set!。从技术上说，执行输入输出的过程也有副作用，但它们不遵守这条规则。

程序员应尽可能在自己的代码中遵守这些规定。

1.3 排版和符号规定

如果一个标准过程或者语法形式的唯一功能是产生一些副作用——比如set!，那么它的返回值是未定义的。这意味着实现可以返回任何数值、任何Scheme对象，以作为过程或语法形式的值。不要指望不同实现返回相同的值，同一实现的不同版本也不用指望，甚至是过程或语法形式的两次使用中，值都可能不一样。某些Scheme系统会使用特殊对象来表示未指定的值。交互式Scheme系统通常会禁止输出此对象，因此返回未指定值的表达式的值无法输出。

虽然大多数标准过程只返回一个值，但使用5.8节中描述的机制，Scheme过程可以不返回值，或者返回一个、多个，甚至可变数量的值。如果某些标准表达式的子表达式之一能求多个值，比如调用返回多值的过程，则它们也可以求多个值。这种情况下，一般说表达式返回“多个值”，而不是简单地说返回子表达式的“值”。同样，将返回“调用参数所返回的值”的标准过程称为“返回过程参数返回的多个值”。

本书使用词语“必须”和“应该”来描述程序要求，例如在调用vector-ref时，要求提供小于矢量长度的索引 。如果使用“必须”，则表示该要求由实现强制执行，即一定会引发异常，通常使用条件类型&assertion。如果使用了“应该”一词，则可能会引发异常，也可能不会。如果未引发异常，则程序的行为是未定义的。

短语“语法错误”用于形容程序格式错误。语法冲突会在程序执行之前被检测到。一但出现， 会引发&syntax类型的异常，并且程序不执行。

本书中使用的排版规定非常简单。所有Scheme对象均以打印字体输出，就像要在键盘上输入一样。Scheme对象包括语法关键字，变量，常量对象，Scheme表达式和示例程序。斜体用于在语法形式的描述中突出语法变量，在过程的描述中突出参数。斜体还可以突出首次出现的专业词汇。一般而言，即使在句子开头，语法形式和过程的名称也不会大写，用斜体写的语法变量也一样。

在语法形式或过程的描述中，原型模式会显示语法形式或正确的参数个数。关键字或过程名称，包括括号，都以打印字体给出。剩下的语法或自变量以斜体显示，用的名称包含语法形式或过程所期望的表达式或自变量的类型。省略号用于表示子表达式或参数零次或多次出现。例如，(or expr ...)描述了具有零个或多个子表达式的or语法形式，而 (member obj list)描述了member过程，它需要两个参数——一个对象和一个列表。

如果语法形式的结构与其原型不匹配，则会发生语法错误。同样，如果传递给标准过程的参数数量与指定要接收的数量不匹配，则会引发条件类型为&assertion的异常。如果标准过程接接收到的参数类型不符合要求，也会引发&assertion异常。例如，vector-set!的原型是：

(vector-set! vecotr n obj)

描述说，n必须是一个小于vector长度的精确非负整数。这样，vector-set!必须接收三个参数，第一个参数必须是向量，第二个参数必须是小于向量长度的精确非负整数，第三个参数可以是任何Scheme值。否则，将引发条件类型为&assertion的异常。

在大多数情况下，所需的参数类型很明显，例如vector，obj或binary-input-port。其他情况下，主要在数字例程的描述中，可以使用缩写，例如int表示整数，exint表示精确整数，fx表示固定整数。在包含受影响条目的各节开头，对这些缩写进行了说明。